472. Concatenated Words

Posted on | Edited on | Views:

LeetCode

link
139. Word Break
DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// O(N * L^3)
class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> result = new ArrayList<>();
        Set<String> preWords = new HashSet<>();
        Arrays.sort(words,(s1, s2) -> 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 s, Set<String> wordDictSet) {
        if(s.length()==0) return false;
        boolean[] dp=new boolean[s.length()+1];
        dp[0]=true;
        for(int i=0;i<s.length();i++){
            for(int j=0;j<=i;j++){
                if(dp[j]&&wordDictSet.contains(s.substring(j,i+1))){
                    dp[i+1]=true;
                    break; //dp[i+1]=true, then move to the next character.
                }
            }
        }
        return dp[s.length()];
    }
}

link
Trie + DFS solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd;
}

class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> res = new ArrayList<String>();
        if (words == null || words.length == 0) return res;

        TrieNode root = new TrieNode();

        for (String word : words) { // construct Trie tree
            if (word.length() == 0) {
                continue;
            }
            buildTrie(word, root);
        }

        for (String word : words) { // test word is a concatenated word or not
            if (word.length() == 0) {
                continue;
            }
            if (testWord(word.toCharArray(), 0, root, 0)) {
                res.add(word);
            }
        }

        return res;
    }

    public boolean testWord(char[] chars, int index, TrieNode root, int count) {
        TrieNode p = root;
        int n = chars.length;
        for (int i = index; i < n; i++) {
            if (p.children[chars[i] - 'a'] == null) {
                return false;
            }
            if (p.children[chars[i] - 'a'].isEnd) {
                if (i == n - 1) { // no next word, so test count to get result.
                    return count > 0;
                }
                if (testWord(chars, i + 1, root, count + 1)) {
                    return true;
                }
            }
            p = p.children[chars[i] - 'a'];
        }
        return false;
    }

    public void buildTrie(String str, TrieNode root) {
        TrieNode p = root;
        for (char c : str.toCharArray()) {
            if (p.children[c - 'a'] == null) {
                p.children[c - 'a'] = new TrieNode();
            }
            p = p.children[c - 'a'];
        }
        p.isEnd = true;
    }
}

0%