472 Concatenated Words 连接词
Description:
Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words in the given array.
Example:
Example 1:
Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats";
"dogcatsdog" can be concatenated by "dog", "cats" and "dog";
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".
Example 2:
Input: words = ["cat","dog","catdog"]
Output: ["catdog"]
Constraints:
1 <= words.length <= 10^4
0 <= words[i].length <= 1000
words[i] consists of only lowercase English letters.
0 <= sum(words[i].length) <= 6 * 10^5
题目描述:
给定一个 不含重复 单词的字符串数组 words ，编写一个程序，返回 words 中的所有 连接词 。
连接词 的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。
示例 :
示例 1：
输入：words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
输出：["catsdogcats","dogcatsdog","ratcatdogcat"]
解释："catsdogcats"由"cats", "dog" 和 "cats"组成;
"dogcatsdog"由"dog", "cats"和"dog"组成;
"ratcatdogcat"由"rat", "cat", "dog"和"cat"组成。
示例 2：
输入：words = ["cat","dog","catdog"]
输出：["catdog"]
提示:
1 <= words.length <= 10^4
0 <= words[i].length <= 1000
words[i] 仅由小写字母组成
0 <= sum(words[i].length) <= 6 * 10^5
思路:
前缀树 Trie
先建立每个单词的前缀树
按照字符串的长度进行排序
先搜索短的, 如果搜索到单词结尾, 搜索剩下的字符串是否也在前缀树中
时间复杂度O(nlgn * m ^ 3), 空间复杂度O(n), 其中 n为单词数, m为单词的最长的长度
代码:
C++:
struct Trie
{
bool word;
struct Trie* next[26]{nullptr};
};
class Solution
{
public:
vector<string> findAllConcatenatedWordsInADict(vector<string>& words)
{
sort(words.begin(), words.end(), [](auto &a, auto &b) { return a.size() < b.size(); });
vector<string> result;
for (auto &word: words)
{
if (word.empty()) continue;
if (search(word)) result.emplace_back(word);
else insert(word);
}
return result;
}
private:
Trie* root = new Trie();
bool search(string &word)
{
Trie *cur = root;
if (word.empty()) return true;
for (int i = 0, n = word.size(), c; i < n; i++)
{
c = word[i] - 'a';
string child = word.substr(i + 1);
if (!cur -> next[c]) return false;
if (cur -> next[c] -> word) if (search(child)) return true;
cur = cur -> next[c];
}
return false;
}
void insert(string &word)
{
Trie *cur = root;
for (int i = 0, n = word.size(), c; i < n; i++)
{
c = word[i] - 'a';
if (!cur -> next[c]) cur -> next[c] = new Trie();
cur = cur -> next[c];
}
cur -> word = true;
}
};
Java:
class Trie {
public boolean word = false;
public Trie[] next = new Trie[26];
}
class Solution {
Trie root = new Trie();
public List<String> findAllConcatenatedWordsInADict(String[] words) {
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String a, String b) {
return a.length() - b.length();
}
});
List<String> result = new ArrayList<>();
for (String word: words) {
if (word.length() == 0) continue;
if (search(word)) result.add(word);
else insert(word);
}
return result;
}
public boolean search(String word) {
Trie cur = root;
int n = word.length();
if (n == 0) return true;
for (int i = 0, c; i < n; i++) {
c = word.charAt(i) - 'a';
if (cur.next[c] == null) return false;
if (cur.next[c].word) if (search(word.substring(i + 1))) return true;
cur = cur.next[c];
}
return false;
}
public void insert(String word) {
Trie cur = root;
for (int i = 0, n = word.length(), c; i < n; i++) {
c = word.charAt(i) - 'a';
if (cur.next[c] == null) cur.next[c] = new Trie();
cur = cur.next[c];
}
cur.word = true;
}
}
Python:
class Solution:
class Trie:
def __init__(self):
self.next = [None] * 26
self.word = False
def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
words.sort(key=len)
root = self.Trie()
result = []
def search(word: str) -> bool:
if not word:
return True
cur, n = root, len(word)
for i in range(n):
c = ord(word[i]) - ord('a')
if not cur.next[c]:
return False
if cur.next[c].word:
if search(word[i + 1:]):
return True
cur = cur.next[c]
return False
def insert(word: str) -> None:
cur, n = root, len(word)
for i in range(n):
c = ord(word[i]) - ord('a')
if not cur.next[c]:
cur.next[c] = self.Trie()
cur = cur.next[c]
cur.word = True
for word in words:
if not word:
continue
if search(word):
result.append(word)
else:
insert(word)
return result
