LeetCode 720. 词典中最长的单词
给出一个字符串数组 words 组成的一本英语词典。返回 words 中最长的一个单词，该单词是由 words 词典中其他单词逐步添加一个字母组成。
若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。
示例 1：
输入：words = ["w","wo","wor","worl", "world"]
输出："world"
解释： 单词"world"可由"w", "wo", "wor", 和 "worl"逐步添加一个字母组成。示例 2：
输入：words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
输出："apple"
解释："apply" 和 "apple" 都能由词典中的单词组成。但是 "apple" 的字典序小于 "apply" method 1: 哈希表
排序：如果长度相同，按字典序拍，否则长的排前面，这样第一个满足条件的就是结果
字典存哈希表中，遍历字符串的每个子串看在不在哈希表中
static bool cmp(const string& a, const string& b) {
if (a.size() == b.size()) return a < b;
return a.size() > b.size();
}
unordered_set<string> st;
bool dfs(string& s) {
for (int i = 1; i < s.size(); i++) {
if (st.count(s.substr(0, i)) == 0) return false;
}
return true;
}
string longestWord(vector<string>& words) {
for (auto w : words) st.insert(w);
sort(words.begin(), words.end(), cmp);
for (auto word : words) {
if (dfs(word)) {
return word;
}
}
return "";
}也可以不排序
string longestWord(vector<string>& words) {
for (auto w : words) st.insert(w);
string res;
for (auto word : words) {
if (word.size() < res.size() || (word.size() == res.size() && word > res)) continue; // 剪枝
if (dfs(word)) res = word;
}
return res;
}method 2: Trie树
用Trie树可以方便得查找一个字符串的所有子串是否在字典中
如果某个前缀的isEnd=false，说明字典中没有这个前缀单词，直接返回
class Trie {
public:
vector<Trie*> next;
bool isEnd;
Trie(): next(26), isEnd(false) {}
void insert(string s) {
Trie *root = this;
for (auto c : s) {
if (!root->next[c - 'a']) {
root->next[c - 'a'] = new Trie();
}
root = root->next[c - 'a'];
}
root->isEnd = true;
}
bool search(string s) {
Trie *root = this;
for (auto c : s) {
if (!root->next[c - 'a'] || !root->next[c - 'a']->isEnd) return false;
root = root->next[c - 'a'];
}
return true;
}
};
class Solution {
public:
string longestWord(vector<string>& words) {
Trie trie;
for (auto w : words) trie.insert(w);
string res;
for (auto word : words) {
if (word.size() < res.size() || (word.size() == res.size() && word > res)) continue;
if (trie.search(word)) {
res = word;
}
}
return res;
}
};面试题 17.15. 最长单词
给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。
示例：
输入： ["cat","banana","dog","nana","walk","walker","dogwalker"]
输出： "dogwalker"
解释： "dogwalker"可由"dog"和"walker"组成。method
跟上题不同的是，这里换成字符串要由字典中的单词组成，而且不能是自己，所以用排序，然后把自己移除
用DFS找分割每个子串是否可以找到对应单词
static bool cmp(const string& a, const string& b) {
if (a.size() == b.size()) return a < b;
return a.size() > b.size();
}
unordered_set<string> st;
bool dfs(string s) {
if (st.count(s)) return true;
for (int i = 1; i <= s.size(); i++) {
if (st.count(s.substr(0, i))) { // 找从0开始的子串，如果s[0:i)可以，就递归找剩下的s[i:n-1]
if (dfs(s.substr(i))) return true;
}
}
return false;
}
string longestWord(vector<string>& words) {
for (auto w : words) st.insert(w);
sort(words.begin(), words.end(), cmp);
for (auto word : words) {
st.erase(word); // 移除，不然会找到自己
if (dfs(word)) {
return word;
}
}
return "";
}
