[leetcode] sticker spelling (dynamic planning)

691. Sticker spelling - Power button （LeetCode）

One 、 subject

We have n Different stickers . Each sticker has a small English word .

You want to spell the given string target , The method is to cut individual letters from the collected stickers and rearrange them . If you will , You can use each sticker multiple times , The number of each sticker is unlimited .

Back you need to spell target  Minimum number of stickers . If the task is not possible , Then return to -1 .

Be careful ： In all test cases , All the words are from 1000 A random selection of the most common American English words , also target  Selected as a connection between two random words .

Example 1：
Input ： stickers = ["with","example","science"], target = "thehat"
Output ：3
explain ：
We can use 2 individual "with" stickers , and 1 individual "example" stickers .
Cut and rearrange the letters on the sticker , You can form goals “thehat“ 了 .
Besides , This is the minimum number of stickers required to form the target string .

Example 2：
Input ：stickers = ["notice","possible"], target = "basicbasic"
Output ：-1
explain ： We can't form goals by cutting the letters of a given sticker “basicbasic”.

Tips ：

• n == stickers.length
• 1 <= n <= 50
• 1 <= stickers[i].length <= 10
• 1 <= target.length <= 15
• stickers[i]  and  target  Made up of lowercase English words

Two 、 Code

class Solution {
    public int minStickers(String[] stickers, String target) {
        //  Count the word frequency of stickers  scount[i] It means the first one i The number of word frequencies of each letter on the poster . This topic has nothing to do with the order of characters , Only related to the number of characters 
        int[][] scount = new int[stickers.length][26];
        for (int i = 0; i < stickers.length; i++) {
            char[] tchars = stickers[i].toCharArray();
            
            for (int j = 0; j < tchars.length; j++) {
                scount[i][tchars[j] - 'a']++;
            }
        }

        //  Here, the word frequency statistics of the target string cannot be used as recursive parameters , because dp It's a HashMap, its key You need to use an object to uniquely identify , Only strings can do this 
        // int[] tcount = new int[26];
        // char[] targetChars = target.toCharArray();
        // for (int i = 0; i < targetChars.length; i++) {
        //     tcount[targetChars[i] - 'a']++;
        // }

        HashMap<String, Integer> dp = new HashMap<>();

        int min = process(scount, target, dp);

        //  If the maximum value of the system is returned , Indicates that the target string cannot be formed 
        return min == Integer.MAX_VALUE ? -1 : process(scount, target, dp);
    }
    public int process(int[][] scount, String rest, HashMap<String, Integer> dp) {
        //  If there are already calculated results , Just take it out and use it 
        if (dp.containsKey(rest)) {
            return dp.get(rest);
        }

        //  If the remaining target characters are empty , There is no need for stickers , Go straight back to 0 Post paper 
        if (rest.length() == 0) {
            return 0;
        }

        //  Count the word frequency of the target string 
        int[] tcount = new int[26];
        char[] targetChars = rest.toCharArray();
        for (int i = 0; i < targetChars.length; i++) {
            tcount[targetChars[i] - 'a']++;
        }

        int min = Integer.MAX_VALUE;
        for (int i = 0; i < scount.length; i++) {
            //  Only the sticker with the first character in the current target string will enter the recursive Branch . This operation is pruning optimization , Reduce unnecessary repeated recursive branches . This operation does not impress the final result , But it can reduce the number of recursive branches , Improve execution efficiency 
            if (scount[i][targetChars[0] - 'a'] > 0) {
                
                //  Offset the characters of the target string with the characters of the sticker , And generate a new target string 
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < 26; j++) {
                    int num = tcount[j] - scount[i][j];
                    //  Be careful ,tcount Is the data in the stack , I'll use it again in the next cycle , It cannot be modified here 
                    //tcount[j] -= scount[i][j];
                    for (int k = 0; k < num; k++) {
                        sb.append((char) (j + 'a'));
                    }
                }
                String nextRest = sb.toString();

                //  Minimum value 
                min = Math.min(min, process(scount, nextRest, dp));
            }
        }
        //  In the above loop, the number of the first sticker of each recursive branch is underestimated , So we need to add 1. If min Still empty , Description the target string cannot be combined 
        min += (min ==  Integer.MAX_VALUE ? 0 : 1);
        //  Put in dp recorded 
        dp.put(rest, min);
        return min;
    }
}

3、 ... and 、 Their thinking  

Note that each sticker on this topic is infinite , Use as many as you want , As long as it can spell the final target string . So this question has nothing to do with the order of characters , Only related to the number of characters .

Use memory search , Store the calculated results in dp in , Shoulder to shoulder double counting . This problem uses pruning skills in the recursive process , Reduce unnecessary recursive branches , Improve execution efficiency .