472. Concatenated Words

Version #2 DP

39.76 %
class Solution {
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
Set<String> dict = new HashSet<>();
List<String> result = new ArrayList<>();
Arrays.sort(words, Comparator.comparing(String::length));
for (String word : words) {
int len = word.length();
if (len > 0) {
boolean[] isValid = new boolean[len + 1]; // substring[0, i) is valid
isValid[0] = true;
for (int j = 1; j <= len; j++) {
for (int i = j - 1; i >= 0; i--) {
if (isValid[i] && dict.contains(word.substring(i, j))) {
isValid[j] = true;
                            break;
}
}
}
if (isValid[len]) {
result.add(word);
}
}
dict.add(word);
}
return result;
}
}

Version #1 Trie + DFS


67.07 %

class Solution {
    class TrieNode {
String word;
TrieNode[] children;
public TrieNode() {
this.children = new TrieNode[26];
}
}


private void addWord(TrieNode root, String source) {
TrieNode curr = root;
for (int i = 0; i < source.length(); i++) {
int index = source.charAt(i) - 'a';
if (curr.children[index] == null) {
curr.children[index] = new TrieNode();
}
curr = curr.children[index];
}
curr.word = source;
}

public List<String> findAllConcatenatedWordsInADict(String[] words) {
TrieNode root = new TrieNode();
for (String word : words) {
addWord(root, word);
}
List<String> result = new ArrayList<>();
for (String word : words) {
if (word.length() > 0 && check(root, word, 0, new HashSet<>())) {
result.add(word);
}
}
return result;
}

// Given a string, find all valid prefixes in trie
private boolean check(TrieNode root, String target, int startIndex, Set<Integer> visited) {
if (visited.contains(startIndex)) {
return false;
}
if (startIndex == target.length()) {
return true;
}
TrieNode curr = root;
for (int i = startIndex; i < target.length(); i++) {
TrieNode next = curr.children[target.charAt(i) - 'a'];
if (next == null) { // no more valid chars
break;
}
if (next.word != null && !(startIndex == 0 && i == target.length() - 1)) {// one validPrefix found
if (check(root, target, i + 1, visited)) {
return true;
}
visited.add(i + 1);
}
curr = next;
}
return false;
}
}