算法笔记之字典树——连接词

又是一个字典树（trie）问题，其实字典树的思路不难想到，但是本体的细节很巧妙，而且一些用例比较阴间，需要注意的地方多。

题目描述

LeetCode472. 连接词

给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。

连接词 定义为：一个完全由给定数组中的至少两个较短单词组成的字符串。

解题思路

主要思路：

• 匹配字符串问题，首先明确要使用字典树。
• 先把words按照单词长度排序，再依次遍历，线查找每个单词是否连接词，然后在插入。这样的好处是不用担心搜索到的单词是它自身。
• 查找的时候需要使用DFS。
• 同时利用记忆化搜索优化效率。

需要注意的一点就是要考虑空字符串这种阴间场景。

Java代码

class Solution {
    private TrieNode root;
    private Map<String, Boolean> memo;
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        Arrays.sort(words, (a, b) -> (a.length() - b.length()));
        root = new TrieNode(0);
        List<String> r = new ArrayList<>();
        memo = new HashMap<>();
        for(int i = 0; i < words.length; i++) {
            if(words[i].length() == 0) { // 跳过空串
                continue;
            }   
            // 先查找
            if(search(words[i], root, 0)) {               
                r.add(words[i]);
            }
            // 这里要注意，单词插入后，记忆化哈希表中一定是true，
            memo.put(words[i], true);
            // 在插入
            add(words[i], root);
        }
        return r;
        
    }

    // 字典树
    class TrieNode {
        public TrieNode[] next;
        public boolean isEnd;
        public int current; // 这个没啥用
        public TrieNode(int current) {
            this.current = current;
            this.next = new TrieNode[26];
        }
    }

    // 向字典树中插入单词
    private void add(String word, TrieNode trie) {
        TrieNode node = trie;
        for(int i = 0; i < word.length(); i++) {
            int c = word.charAt(i) - 'a';
            if(node.next[c] == null) {
                node.next[c] = new TrieNode(c);                
            } 
            node = node.next[c];           
        }
        node.isEnd = true;
    }

    // 在字典树中搜索单词 dfs
    private boolean search(String word, TrieNode trie, int start) {
        if(start == word.length()) {
            if(trie.isEnd) {
                return true;
            } 
            return false;
        }
        int c = word.charAt(start) - 'a';
        if(trie.next[c] == null) {
            return false;
        }
        TrieNode nextNode = trie.next[c];
        // 考虑下一字符属于新单词的场景
        if(nextNode.isEnd) {
            // 只有从开头开始的单词才加入记忆化哈希表
            String now = word.substring(start +1);
            boolean flag = false;
            if(memo.containsKey(now)) {
                flag = memo.get(now);
            } else {
                flag = search(word, root, start + 1);
                memo.put(now, flag);
            }
            
            if(flag) {
                return true;
            }
        }
        boolean f = search(word, nextNode, start + 1);
        return f;
    }
}