Concatenated Words

给一个字符串组, 返回所有在里面的由两个以上字符串拼接组成的字符串. 这个题主要考察剪枝, 首先要查重, 用一个set重新装一下数组, 然后按照字典序排序, 然后逐个看是不是答案, 验证的时候, 每个substring都要看一下, 用一个dp当memo, 记录已经看过的字符串.

public class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> result = new ArrayList<>();
        Set<String> preWords = new HashSet<>();
        Arrays.sort(words, new Comparator<String>() {
            public int compare (String s1, String s2) {
                return s1.length() - s2.length();
            }
        });
        for(int i = 0 ; i < words.length; i++) {
            if(canForm(words[i],preWords))
                result.add(words[i]);
            preWords.add(words[i]);
        }
        return result;
    }
    
    public boolean canForm(String word, Set<String> dict) {
        boolean[] dp = new boolean[word.length() + 1];
        dp[0] = true;
        if(dict.isEmpty())
            return false;
        for(int i = 1;  i <= word.length(); i++) {
            for(int j = 0 ; j < i; j++){
                if(dp[j]&&dict.contains(word.substring(j,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[word.length()];
    }
}