472. Concatenated Words

DFS

class Solution {
    private static final int PRIME = 20220821;

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<Long> wordHashSet = new HashSet<>();
        for (String word : words) {
            wordHashSet.add(hash(word));
        }

        List<String> concatenatedWordList = new ArrayList<>();
        for (String word : words) {
            dfs(concatenatedWordList, wordHashSet, word, 0);
        }

        return concatenatedWordList;
    }

    private boolean dfs(List<String> concatenatedWordList, Set<Long> wordHashSet, String word, int startIndex) {
        // 一个单词可能存在多种切分方法，此处保证同一个单词只添加一次
        if (startIndex == word.length() && (concatenatedWordList.isEmpty() || !concatenatedWordList.get(concatenatedWordList.size() - 1).equals(word))) {
            concatenatedWordList.add(word);
            return true;
        }

        long hash = 0;
        // 保证至少切分一次
        for (int endIndex = startIndex; startIndex == 0 ? endIndex < word.length() - 1 : endIndex < word.length(); endIndex++) {
            hash = hash * PRIME + word.charAt(endIndex);
            if (wordHashSet.contains(hash)) {
                if (dfs(concatenatedWordList, wordHashSet, word, endIndex + 1)) {
                    break; // 剪枝，当前单词已经满足条件，不再继续搜索
                }
            }
        }

        return false;
    }

    private long hash(String word) {
        long hash = 0;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            hash = hash * PRIME + c;
        }
        return hash;
    }
}

DP

class Solution {
    private static final int PRIME = 20220821;

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Set<Long> wordHashSet = new HashSet<>();
        for (String word : words) {
            wordHashSet.add(hash(word));
        }

        List<String> concatenatedWordList = new ArrayList<>();
        for (String word : words) {
            if (isConcatenated(word, wordHashSet)) {
                concatenatedWordList.add(word);
            }
        }

        return concatenatedWordList;
    }

    private boolean isConcatenated(String word, Set<Long> wordHashSet) {
        // 定义 dp[i] 为前 i 个字符最大可由多少个单词组成
        int[] dp = new int[word.length() + 1];
        Arrays.fill(dp, -1); // 初始化，默认都不能由单词组成
        dp[0] = 0;

        // 当前 i 个字符组成的字符串可以由单词组成时，计算前 j 个字符组成的字符串的状态
        for (int i = 0; i <= word.length(); i++) {
            if (dp[i] == -1) {
                // 当前 i 个字符组成的字符串不能由单词组成时，此时不能递推，注意此处为 continue, 即后续的 i 依然要进行计算，此条件也不能归入到 for 循环的判断逻辑中，否则语义将变为 break
                continue;
            }

            long hash = 0;
            // 当前 i 个字符可以由单词组成时，计算前 j 个字符组成的字符串的状态
            for (int j = i + 1; j <= word.length(); j++) {
                hash = hash * PRIME + word.charAt(j - 1); // 注意索引下标
                if (wordHashSet.contains(hash)) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                }
            }

            if (dp[word.length()] > 1) {
                return true;
            }
        }

        return false;
    }

    private long hash(String word) {
        long hash = 0;
        for (int i = 0; i < word.length(); i++) {
            hash = hash * PRIME + word.charAt(i);
        }
        return hash;
    }
}

Trie

class Solution {
    private static class Trie {
        private Trie[] children;
        private boolean end;

        public Trie() {
            this.children = new Trie[26];
            this.end = false;
        }
    }

    private void insertToTrie(String word, Trie trie) {
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            if (trie.children[index] == null) {
                trie.children[index] = new Trie();
            }
            trie = trie.children[index];
        }

        trie.end = true;
    }

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort(words, Comparator.comparingInt(String::length));

        List<String> concatenatedWordList = new ArrayList<>();
        Trie trie = new Trie();
        for (String word : words) {
            if (word.length() == 0) {
                // 空字符串不可能为连接词，跳过
                continue;
            }

            boolean[] visited = new boolean[word.length()];
            if (isConcatenated(trie, word, visited, 0)) {
                concatenatedWordList.add(word);
            } else {
                insertToTrie(word, trie);
            }

        }

        return concatenatedWordList;
    }

    private boolean isConcatenated(Trie trie, String word, boolean[] visited, int startIndex) {
        if (startIndex == word.length()) {
            return true;
        }

        if (visited[startIndex]) {
            return false;
        }
        visited[startIndex] = true;

        Trie node = trie; // 复制引用
        for (int i = startIndex; i < word.length(); i++) {
            int index = word.charAt(i) - 'a';
            node = node.children[index];
            if (node == null) {
                return false;
            }
            
            // 注意搜索下一个单词时要从 trie 的根节点开始搜索
            if (node.end && isConcatenated(trie, word, visited, i + 1)) {
                return true;
            }
        }

        return false;
    }
}

Reference

472. Concatenated Words