leetcode-concatenated-words

发表于   |   分类于 ，   |  

题目大意

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

　　给你一个单词的list，返回list中的满足这样条件的单词：该单词由list中其它至少两个更短的单词拼接组成。

题目分析

　　跟https://leetcode.com/problems/word-break-ii/有类似之处，本题需要借助trie树进行高效的搜索前缀。首先是要将list中的单词建立trie树。search方法返回组成的单词数量，注意如果返回-1，那么就说明该单词无法由list中的单词组成，search方法利用了动态规划，用map进行记忆。

代码

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
class TrieNode {
    public char ch;
    public int freq;
    public TrieNode[] childs;
    public TrieNode() {
        childs = new TrieNode[26];
    }
}
class Trie {
    private TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String s) {
        char[] c = s.toCharArray();
        int len = c.length;
        TrieNode cur = root;
        for (int i = 0; i < len; i++) {
            if (cur.childs[c[i] - 'a'] == null) {
                cur.childs[c[i] - 'a'] = new TrieNode();
            }
            cur = cur.childs[c[i] - 'a'];
            cur.ch = c[i];
            if (i == len - 1) {
                cur.freq++;
            }
        }
    }
    
    public List<Integer> prefixSearch(String s) {
        List<Integer> ans = new ArrayList<Integer>();
        char[] c = s.toCharArray();
        int len = c.length;
        TrieNode cur = root;
        for (int i = 0; i < len; i++) {
            if (cur.childs[c[i] - 'a'] == null) {
                return ans;
            }
            cur = cur.childs[c[i] - 'a'];
            if (cur.freq > 0) {
                ans.add(i);
            }
        }
        return ans;
    }
}
public class Solution {
    
    private Map<String, Integer> map;
    private String[] words;
    private int len;
    private Trie trie;
    
    private int search(String s) { 
        
        if (s.length() == 0) { // 直接找到尾部了
            return 0;
        }
        if (map.containsKey(s)) {
            return map.get(s);
        }
        List<Integer> list = trie.prefixSearch(s);
        if (list.size() == 0) {
            return -1;
        }
        int max = -1;
        for (int i : list) {
            int ret = search(s.substring(i + 1));
            if (ret >= 0) {
                max = Math.max(max, ret + 1);
            }
        }
        map.put(s, max);
        return max;
    }
    
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> ans = new ArrayList<String>();
        this.words = words;
        len = words.length;
        if (len <= 2) {
            return ans;
        }
        Arrays.sort(words);
        trie = new Trie();
        for (String w : words) {
            trie.insert(w);
        }
        map = new HashMap<String, Integer>();
        
        for (int i = 0; i < len; i++) {
            if (search(words[i]) > 1) {
                ans.add(words[i]);
            }
        }
        
        return ans;
    }
}