[snap]compose 2nd string array w

原题

解法这位同学说的很清楚了。

第一个array只有total count是有用信息，数一遍就好了。
第二个array那里可以预处理一下把count先数好，把有字母occurrence大于array 1的total count的那些单词直接扔掉。
然后就类似没有重复的combination sum做个DFS就行了，只是DFS是26个target，combination sum是一个target。
不知道你为什么要建trie，这个问题里完全没有前缀结构啊...

以下代码中利用valid()进行了一些适当的剪枝，由于该数组只有26个元素，因此valid的遍历并不很time-consuming.

public class composeString {


    public List<List<String>> compose(String[] input1,String[] input2){
        List<List<String>> res = new LinkedList<>();


        //use counts array to record the character frequency for each word in input2
        int[][] counts = new int[input2.length][26];

        for ( int i = 0; i < input2.length; i++){
            String s = input2[i];
            for(int j = 0; j < s.length(); j++){
                char c = s.charAt(j);
                counts[i][c - 'A']++;
            }
        }

        //use dic to record the char frequency in input1
        int[] dic = new int[26];
        for(int i = 0; i < input1.length; i++){
            String s = input1[i];
            for(int j = 0; j < s.length(); j++){
                char c = s.charAt(j);
                dic[c - 'A']++;

            }
        }

        helper(dic, 0, counts,input2,new LinkedList<String>(),res);

        return res;



    }

    public void helper(int[] dic, int start, int[][] counts,String[] input2, List<String> path, List<List<String>> ans){

        if(start == input2.length){

            if(valid(dic) == 0)ans.add(new LinkedList<String>(path));
                return;
        }




        // add start

        int[] count = counts[start];
        for(int i = 0; i < 26; i++){
            dic[i] -= count[i];
        }

        if(valid(dic) >= 0){
            path.add(input2[start]);
            helper(dic,start + 1, counts, input2,path,ans);
            path.remove(path.size() - 1);
        }

        for(int i = 0; i < 26; i++){
            dic[i] += count[i];
        }

        helper(dic,start + 1, counts, input2, path, ans);


    }

    //check the status of dic, 0 means all unit is 0, 1 means all unit is >= 0, -1 means some chars has been used up, < 0.
    public int valid(int[] dic){
        int res = 0;
        for(int i : dic){
            if(i < 0)return -1;
            res += i;
        }
        return res;
    }


    public static void main(String[] args){
        composeString cs = new composeString();
        System.out.println(cs.compose(new String[]{"CAT", "DOG"},new String[]{"GAT","DOC","CD","GOAT","BAD","COOL"}));
    }





}