动态规划之贴纸拼词问题

题目

我们有 n 不同的贴纸。每张贴纸上都有一个小写英文单词。

你想拼写给定的字符串 target，方法是从收集到的贴纸中切割单个字母并重新排列。如果你愿意，你可以多次使用每个贴纸，每个贴纸的数量是无限的。

你需要拼出来才能回来 target的最小贴纸数量。如果任务不可能，返回 -1 。

注：在所有测试用例中，所有单词都来自 1000 在最常见的美国英语单词中随机选择， target被选为连接两个随机单词。

leetcode链接

每张贴纸分别与标签目标字符匹配，查看剩余标签字符，不断循环，找出最低值。如下图所示：

public static int spellWordOne(String target, String[] strs){    ///边界情况    if(target == null || target.length() == 0 || strs == null || strs.length == 0){        return 0;    }    //返回结果    int result = stickerToSpellWordOne(target, strs);    /如果result， == Integer.MAX_VALUE，说明不存在，直接返回-1    return result == Integer.MAX_VALUE ? -1 : result;}public static int stickerToSpellWordOne(String target, String[] strs){    if(target.length() == 0){        return 0;    }    ////用于比较值的大小    int min = Integer.MAX_VALUE;    ///数组中的每个贴纸作为第一值处理一次    for (String str : strs) {        //与目标字符串对比，剩下的目标字符串是rest        String rest = deal(target, str);        //如果长度相等 这意味着没有变化。不要这个str。如果你想要它，你只会增加贴纸的数量        if(rest.length() != target.length()){            min = Math.min(min, stickerToSpellWordOne(rest, strs));        }    }    //因为第一个字符不算 所以 + 1，strs中有可能根本没有符合要求的卡    return min + (min == Integer.MAX_VALUE ? 0 : 1);}public static String deal(String target, String str){    //字符串分为数组    char[] targets = target.toCharArray();    char[] strs = str.toCharArray();    //新建统计数组，统计target 和 str比较后剩余字符的剩余字符    int[] count = new int[26];    ///统计targets    for (int i = 0; i < targets.length; i++) {        int value = targets[i] - 'a';        count[value] ++;    }    //统计strs    for (int i = 0; i < strs.length; i++) {        int value = strs[i] - 'a';        count[value] --;    }    ///拼接字符串返回    StringBuilder sb = new StringBuilder();    for (int i = 0; i < 26; i++) {        // > 0 只有说明有剩余的        if(count[i] > 0){            for (int j = 0; j < count[i]; j++) {                sb.append((char)(i + 'a'));            }        }    }    return sb.toString();}

这一步最重要的是贪婪。只有字符串数组中的子字符包含目标字符（剩余目标字符）的第一个字符才能一次删除。

//方法二:词频统计publicc: static int spellWordTwo(String target, String[] strs){    ///边界情况    if(target == null || target.length() == 0 || strs == null || strs.length == 0){        return 0;    }    int N = strs.length;    //用词频表代替贴纸数组，用counts记录字符串数组中每个子数组中字母的次数    int[][] counts = new int[N][26];    for (int i = 0; i < N; i++) {        char[] chars = strs[i].toCharArray();        for (int j = 0; j < chars.length; j++) {            counts[i][chars[j] - 'a'] ++;        }    }    //返回结果    int result = stickerToSpellWordTwo(target, counts);    /如果result， == Integer.MAX_VALUE，说明不存在，直接返回-1    return result == Integer.MAX_VALUE ? -1 : result;}public static int stickerToSpellWordTwo(String target, int[][] counts){    if(target.length() == 0){        return 0;    }    ////用于比较值的大小    int min = Integer.MAX_VALUE;    ///先统计剩余target字符串中字符的数量    char[] chars = target.toCharArray();    int[] tcounts = new int[26];    for (int i = 0; i < target.length(); i++) {        tcounts[chars[i] - 'a'] ++;    }    //字符数组长度N    int N = counts.length;    for (int i = 0; i < N; i++) {        //取出一张贴纸        int[] count = counts[i];        ///当目标字符串中的第一个字符在时 只在count中进行，        // 相当于，如果字符数组中的子字符串包含目标数组的第一个字符，则继续下去，因为总有子字符包含，或者不包括        if(count[chars[0] - 'a'] > 0){            StringBuilder builder = new StringBuilder();            for (int j = 0; j < 26; j++) {                ///目标数组有值                if(tcounts[j] > 0){                    ///这一步主要是消除目标数组中的字符                    int num = tcounts[j] - count[j];                    //如果是负数或0，说明已经没有了，或者目标数组不包含这个字符                    for (int k = 0; k < num; k++) {                        builder.append((char)(j + 'a'));                    }                }            }            ///目前剩余的目标数组            String rest = builder.toString();            min = Math.min(min, stickerToSpellWordTwo(rest, counts));        }    }    //因为第一个字符不算 所以 + 1.strs中可能根本没有符合要求的卡    return min + (min == Integer.MAX_VALUE ? 0 : 1);}

添加一个Hashmap来存储已计算的值

//方法三:傻缓存publicc: static int spellWordThree(String target, String[] strs){    ///边界情况    if(target == null || target.length() == 0 || strs == null || strs.length == 0){        return 0;    }    int N = strs.length;    //用词频表代替贴纸数组，用counts记录字符串数组中每个子数组中字母的次数    int[][] counts = new int[N][26];    for (int i = 0; i < N; i++) {        char[] chars = strs[i].toCharArray();        for (int j = 0; j < chars.length; j++) {            counts[i][chars[j] - 'a'] ++;        }    }    ////用map集成缓存    HashMap<String, Integer> dp = new HashMap<>();    //如果是“”字符，返回0    dp.put("", 0);    int result = stickerToSpellWordThree(target, counts, dp);    /如果result， == Integer.MAX_VALUE，说明不存在，直接返回-1    return result == Integer.MAX_VALUE ? -1 : result;}public static int stickerToSpellWordThree(String target, int[][] counts, HashMap<String, Integer> dp){    if(dp.containsKey(target)){ 字符将返回0        return dp.get(target);    }    ////用于比较值的大小    int min = Integer.MAX_VALUE;    ///先统计剩余target字符串中字符的数量    char[] chars = target.toCharArray();    int[] tcounts = new int[26];    for (int i = 0; i < target.length(); i++) {        tcounts[chars[i] - 'a'] ++;    }    //字符数组长度N    int N = counts.length;    for (int i = 0; i < N; i++) {        //取出一张贴纸        int[] count = counts[i];        ///当目标字符串中的第一个字符在时 只在count中进行，        // 相当于，如果字符数组中的子字符串包含目标数组的第一个字符，则继续下去，因为总有子字符包含，或者不包括        if(count[chars[0] - 'a'] > 0){            StringBuilder builder = new StringBuilder();            for (int j = 0; j < 26; j++) {                ///目标数组有值                if(tcounts[j] > 0){                    ///这一步主要是消除目标数组中的字符                    int num = tcounts[j] - count[j];                    //如果是负数或0，说明已经没有了，或者目标数组不包含这个字符                    for (int k = 0; k < num; k++) {                        builder.append((char)(j + 'a'));                    }                }            }            ///目前剩余的目标数组            String rest = builder.toString();            min = Math.min(min, stickerToSpellWordThree(rest, counts, dp));        }    }    //因为第一个字符不算 所以 + 1.strs中可能根本没有符合要求的卡    int result = min + (min == Integer.MAX_VALUE ? 0 : 1);    //做缓存    dp.put(target, result);    return result;}

public class StickerToSpellWords {    //方法1:暴力递归    public static int spellWordOne(String target, String[] strs){        ///边界情况        if(target == null || target.length() == 0 || strs == null || strs.length == 0){            return 0;        }        //返回结果        int result = stickerToSpellWordOne(target, strs);        /如果result， == Integer.MAX_VALUE，说明不存在，直接返回-1        return result == Integer.MAX_VALUE ? -1 : result;    }    public static int stickerToSpellWordOne(String target, String[] strs){        if(target.length() == 0){            return 0;        }        ////用于比较值的大小        int min = Integer.MAX_VALUE;        ///数组中的每个贴纸作为第一值处理一次        for (String str : strs) {            //与目标字符串对比，剩下的目标字符串是rest            String rest = deal(target, str);            //如果长度相等 这意味着没有变化。不要这个str。如果你想要它，你只会增加贴纸的数量            if(rest.length() != target.length()){                min = Math.min(min, stickerToSpellWordOne(rest, strs));            }        }        //因为第一个字符不算 所以 + 1，strs中有可能根本没有符合要求的卡        return min + (min == Integer.MAX_VALUE ? 0 : 1);    }    public static String deal(String target, String str){        //字符串分为数组        char[] targets = target.toCharArray();        char[] strs = str.toCharArray();        //新建统计数组，统计target 和 str比较后剩余字符的剩余字符        int[] count = new int[26];        ///统计targets        for (int i = 0; i < targets.length; i++) {            int value = targets[i] - 'a';            count[value] ++;        }        //统计strs        for (int i = 0; i < strs.length; i++) {            int value = strs[i] - 'a';            count[value] --;        }        ///拼接字符串返回        StringBuilder sb = new StringBuilder();        for (int i = 0; i < 26; i++) {            // > 0 只有说明有剩余的            if(count[i] > 0){                for (int j = 0; j < count[i]; j++) {                    sb.append((char)(i + 'a'));                }            }        }        return sb.toString();    }    //方法二:词频统计    public static int spellWordTwo(String target, String[] strs){        ///边界情况        if(target == null || target.length() == 0 || strs == null || strs.length == 0){            return 0;        }        int N = strs.length;        //用词频表代替贴纸数组，用counts记录字符串数组中每个子数组中字母的次数        int[][] counts = new int[N][26];        for (int i = 0; i < N; i++) {            char[] chars = strs[i].toCharArray();            for (int j = 0; j < chars.length; j++) {                counts[i][chars[j] - 'a'] ++;            }        }        //返回结果        int result = stickerToSpellWordTwo(target, counts);        /如果result， == Integer.MAX_VALUE，说明不存在，直接返回-1        return result == Integer.MAX_VALUE ? -1 : result;    }    public static int stickerToSpellWordTwo(String target, int[][] counts){        if(target.length() == 0){            return 0;        }        ////用于比较值的大小        int min = Integer.MAX_VALUE;        ///先统计剩余target字符串中字符的数量        char[] chars = target.toCharArray();        int[] tcounts = new int[26];        for (int i = 0; i < target.length(); i++) {            tcounts[chars[i] - 'a'] ++;        }        //字符数组长度N        int N = counts.length;        for (int i = 0; i < N; i++) {            //取出一张贴纸            int[] count = counts[i];            ///当目标字符串中的第一个字符在时 只在count中进行，            // 相当于，如果字符数组中的子字符串包含目标数组的第一个字符，则继续下去，因为总有子字符包含，或者不包括            if(count[chars[0] - 'a'] > 0){                StringBuilder builder = new StringBuilder();                for (int j = 0; j < 26; j++) {                    ///目标数组有值                    if(tcounts[j] > 0){                        ///这一步主要是消除目标数组中的字符                        int num = tcounts[j] - count[j];                        //如果是负数或0，说明已经没有了，或者目标数组不包含这个字符                        for (int k = 0; k < num; k++) {                            builder.append((char)(j + 'a'));                        }                    }                }                ///目前剩余的目标数组                String rest = builder.toString();                min = Math.min(min, stickerToSpellWordTwo(rest, counts));            }        }        //因为第一个字符不算 所以 + 1，strs中有可能根本没有符合要求的卡        return min + (min == Integer.MAX_VALUE ? 0 : 1);    }    //方法三：傻缓存    public static int spellWordThree(String target, String[] strs){        ///边界情况        if(target == null || target.length() == 0 || strs == null || strs.length == 0){            return 0;        }        int N = strs.length;        //用词频表代替贴纸数组，用counts记录字符串数组中每个子数组中字母的次数        int[][] counts = new int[N][26];        for (int i = 0; i < N; i++) {            char[] chars = strs[i].toCharArray();            for (int j = 0; j < chars.length; j++) {                counts[i][chars[j] - 'a'] ++;            }        }        ////用map集成缓存        HashMap<String, Integer> dp = new HashMap<>();        //如果是“”字符，返回0        dp.put("", 0);        int result = stickerToSpellWordThree(target, counts, dp);        /如果result， == Integer.MAX_VALUE，说明不存在，直接返回-1        return result == Integer.MAX_VALUE ? -1 : result;    }    public static int stickerToSpellWordThree(String target, int[][] counts, HashMap<String, Integer> dp){        if(dp.containsKey(target)){ 字符将返回0            return dp.get(target);        }        ////用于比较值的大小        int min = Integer.MAX_VALUE;        ///先统计剩余target字符串中字符的数量        char[] chars = target.toCharArray();        int[] tcounts = new int[26];        for (int i = 0; i < target.length(); i++) {            tcounts[chars[i] - 'a'] ++;        }        //字符数组长度N        int N = counts.length;        for (int i = 0; i < N; i++) {            //取出一张贴纸            int[] count = counts[i];            ///当目标字符串中的第一个字符在时 只在count中进行，            // 相当于，如果字符数组中的子字符串包含目标数组的第一个字符，则继续下去，因为总有子字符包含，或者不包括            if(count[chars[0] - 'a'] > 0){                StringBuilder builder = new StringBuilder();                for (int j = 0; j < 26; j++) {                    ///目标数组有值                    if(tcounts[j] > 0){                        ///这一步主要是消除目标数组中的字符                        int num = tcounts[j] - count[j];                        //如果是负数或0，说明已经没有了，或者目标数组不包含这个字符                        for (int k = 0; k < num; k++) {                            builder.append((char)(j + 'a'));                        }                    }                }                ///目前剩余的目标数组                String rest = builder.toString();                min = Math.min(min, stickerToSpellWordThree(rest, counts, dp));            }        }        //因为第一个字符不算 所以 + 1，strs中有可能根本没有符合要求的卡        int result = min + (min == Integer.MAX_VALUE ? 0 : 1);        //做缓存        dp.put(target, result);        return result;    }    public static String[] genetateStringArray(int maxSize){        if(maxSize == 0){            return null;        }        String[] strs = new String[maxSize];        for (int i = 0; i < maxSize; i++) {            ///字符串长度            int maxValue = (int)(21 * Math.random());            StringBuilder builder = new StringBuilder();            for (int j = 0; j < maxValue; j++) {               char sign = (char)(26*Math.random() + 'a');               builder.append(sign);            }            strs[i] = builder.toString();        }        return strs;    }    public static void main(String[] args) {        System.out.println(测试开始:;        for (int j = 0; j < 10000; j++) {            ///字符数组长度            int maxSize = (int)(101 * Math.random());            String[] strs = genetateStringArray(maxSize);            int targetSize = (int)(21*Math.random());            StringBuilder builder = new StringBuilder();            for (int i = 0; i < targetSize; i++) {                char sign = (char)(26*Math.random() + 'a');                builder.append(sign);            }            String target = builder.toString();            int resultOne = spellWordOne(target, strs);            int resultTwo = spellWordTwo(target, strs);            int resultTree = spellWordThree(target, strs);            if(resultOne != resultTwo || resultOne != resultTree || resultTwo != resultTree){                System.out.println(“对不起，这次真的不行！！！");                break;            }        }        System.out.println(“测试结束”;    }}