力扣 691 贴纸拼词

题意：给一个字符串，一个字符，最少能用字符串中的几个substring拼出字符

思路：dfs遍历找出最小的合法值

思想：dfs

复杂度：时间O（n＊n)，空间O(n)

class Solution {
    public int minStickers(String[] stickers, String target) {
        int[][] sc = new int[stickers.length][26];
        // 把每一个字符的字符数目找出
        for(int i=0;i<stickers.length;i++)
            sc[i] = findWordCount(stickers[i]);
        // 记录组成key字符，最少用value个字符串中的substring
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        return dfs(sc,target,map);
    }
    // 找出每一个字符串的字符数目
    public int[] findWordCount(String s){
        int[] charSet = new int[26];
        for(char c:s.toCharArray())
            charSet[c-'a']++;
        return charSet;
    }
    // 返回组成t字符，最少需要用几个字符串中的substring
    public int dfs(int[][] sc,String t,HashMap<String,Integer> map){
        // t为0返回0
        if(t.length()==0)
            return 0;
        // t在之前找到过，返回之前的值
        if(map.containsKey(t))
            return map.get(t);
        
        int max = -1;
        int[] tc = findWordCount(t);
        // 对每一个字符串中的字符，dfs，找出使用它能得到的最小字符串值
        for(int[] s:sc){
            // 如果当前字符包含在t内
            if(s[t.charAt(0)-'a']>0){
                // update t字符为新的target
                String next = updateTargetStr(s,tc);
                // dfs找出新的target需要的最小字符串值
                int len = dfs(sc,next,map);
                // 跟新max
                if(len!=-1)
                    max = max==-1?len+1:Math.min(max,len+1);
            }
        }
        // 把当前最小组成t的值放入map
        map.put(t,max);
        return max;
    }
    // 获取剩下的t字符
    public String updateTargetStr(int[] s,int[] t){
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<t.length;i++){
            int j = t[i] - s[i];
            while(j>0){
                sb.append((char)(i+'a'));
                j--;
            }
        }
        return sb.toString();
    }
}