題意：給一個(gè)字符串，一個(gè)字符，最少能用字符串中的幾個(gè)substring拼出字符

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

思想：dfs

復(fù)雜度：時(shí)間O（n＊n)，空間O(n)

class Solution {
    public int minStickers(String[] stickers, String target) {
        int[][] sc = new int[stickers.length][26];
        // 把每一個(gè)字符的字符數(shù)目找出
        for(int i=0;i<stickers.length;i++)
            sc[i] = findWordCount(stickers[i]);
        // 記錄組成key字符，最少用value個(gè)字符串中的substring
        HashMap<String,Integer> map = new HashMap<String,Integer>();
        return dfs(sc,target,map);
    }
    // 找出每一個(gè)字符串的字符數(shù)目
    public int[] findWordCount(String s){
        int[] charSet = new int[26];
        for(char c:s.toCharArray())
            charSet[c-'a']++;
        return charSet;
    }
    // 返回組成t字符，最少需要用幾個(gè)字符串中的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);
        // 對(duì)每一個(gè)字符串中的字符，dfs，找出使用它能得到的最小字符串值
        for(int[] s:sc){
            // 如果當(dāng)前字符包含在t內(nèi)
            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);
            }
        }
        // 把當(dāng)前最小組成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();
    }
}