472 concatenated words

https://leetcode.com/problems/concatenated-words/description/

最简单粗暴的方式就是对每个word用一遍wordbreak，但是记得用之前要把word本身移除掉，我本来以为会超时的没有考虑这种方法，没想到居然过了

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        int n = words.length;
        Set<String> dic = new HashSet<>();
        for (String word : words) {
            dic.add(word);
        }
        List<String> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            dic.remove(words[i]);
            if (wordBreak(words[i], dic)) {
                ans.add(words[i]);
            }
            dic.add(words[i]);
        }
        return ans;
    }
    private boolean wordBreak(String s, Set<String> dic) {
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dic.contains(s.substring(j, i)) && dp[j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}