class Solution {
public:
string longestWord(vector<string>& words) {
}
};
1858. 包含所有前缀的最长单词
给定一个字符串数组 words，找出 words 中所有的前缀都在 words 中的最长字符串。
words = ["a", "app", "ap"]。字符串 "app" 含前缀 "ap" 和 "a" ，都在 words 中。返回符合上述要求的字符串。如果存在多个（符合条件的）相同长度的字符串，返回字典序中最小的字符串，如果这样的字符串不存在，返回 ""。
示例 1:
输入： words = ["k","ki","kir","kira", "kiran"] 输出： "kiran" 解释： "kiran" 含前缀 "kira"、 "kir"、 "ki"、 和 "k"，这些前缀都出现在 words 中。
示例 2:
输入： words = ["a", "banana", "app", "appl", "ap", "apply", "apple"] 输出： "apple" 解释： "apple" 和 "apply" 都在 words 中含有各自的所有前缀。 然而，"apple" 在字典序中更小，所以我们返回之。
示例 3:
输入： words = ["abc", "bc", "ab", "qwe"] 输出： ""
提示：
1 <= words.length <= 1051 <= words[i].length <= 1051 <= sum(words[i].length) <= 105原站题解
java 解法, 执行用时: 19 ms, 内存消耗: 68.5 MB, 提交时间: 2023-10-21 20:31:09
class Solution {
class TrieNode {
char c;
TrieNode[] children;
boolean isWord;
public TrieNode(char cc) {
c = cc;
children = new TrieNode[26];
}
}
private TrieNode root;
private String longest;
public String longestWord(String[] words) {
root = new TrieNode('@');
longest = "";
for (String w : words) {
addWord(w);
}
findLongest(new StringBuilder(), root);
return longest;
}
private void addWord(String w) {
TrieNode node = root;
for (int i = 0; i < w.length(); i++) {
char c = w.charAt(i);
if (node.children[c-'a'] == null)
node.children[c-'a'] = new TrieNode(c);
node = node.children[c-'a'];
}
node.isWord = true;
}
private void findLongest(StringBuilder sb, TrieNode root) {
boolean hasChild = false;
for (TrieNode child : root.children) {
if (child != null && child.isWord) {
findLongest(sb.append(child.c), child);
hasChild = true;
sb.deleteCharAt(sb.length() - 1);
}
}
if (!hasChild && sb.length() > longest.length()) {
longest = sb.toString();
}
}
}
golang 解法, 执行用时: 64 ms, 内存消耗: 42.1 MB, 提交时间: 2023-10-21 20:30:54
type trie struct {
son [26]*trie
end bool
}
func longestWord(words []string) (ans string) {
t := &trie{}
for _, w := range words {
o := t
for _, b := range w {
b -= 'a'
if o.son[b] == nil {
o.son[b] = &trie{}
}
o = o.son[b]
}
o.end = true
}
cur := []byte{}
var dfs func(*trie, int)
dfs = func(o *trie, dep int) {
if dep > len(ans) {
ans = string(cur)
}
for i, s := range o.son {
if s != nil && s.end {
cur = append(cur, 'a'+byte(i))
dfs(s, dep+1)
cur = cur[:len(cur)-1]
}
}
}
dfs(t, 0)
return
}
cpp 解法, 执行用时: 116 ms, 内存消耗: 123.8 MB, 提交时间: 2023-10-21 20:30:39
struct TrieNode
{
TrieNode* children[26];
bool isEnd;
TrieNode() : isEnd(false)
{
memset(children, 0, sizeof(TrieNode*)*26);
}
};
struct TrieTree
{
TrieNode* root = new TrieNode();
// 插入并判断是否有效已有字符串覆盖它的所有前缀
bool InsertAndCheck(string& str)
{
// cout << "InsertAndCheck " << str << endl;
// 默认返回有效
int res = true;
int n = str.size();
TrieNode* curr = root;
for (int i = 0; i < n; ++i)
{
if (curr->children[str[i]-'a'] == nullptr)
{
curr->children[str[i]-'a'] = new TrieNode();
}
curr = curr->children[str[i]-'a'];
// 对于非最后一个，即所有前缀，必须有之前单词存在（即isEnd=true）
if (i < n - 1 && !curr->isEnd)
{
res = false;
}
}
// 最后一个字符结点徐设置end
curr->isEnd = true;
return res;
}
};
class Solution {
public:
string longestWord(vector<string>& words) {
// 升序排序
sort(words.begin(), words.end(), [](const string& a, const string& b)
{
if (a.size() != b.size())
{
return a.size() < b.size();
}
else
{
return a > b;
}
});
// for (string word : words)
// {
// cout << word << endl;
// }
// 构建字典树并且返回结果
TrieTree tree;
string res = "";
int n = words.size();
for (int i = 0; i < n; ++i)
{
if (tree.InsertAndCheck(words[i]))
{
res = words[i];
}
}
return res;
}
};
python3 解法, 执行用时: 64 ms, 内存消耗: 18.5 MB, 提交时间: 2023-10-21 20:30:19
class Solution:
def longestWord(self, words: List[str]) -> str:
words.sort(key=lambda s: len(s))
data = {''}
res = ''
for i in words:
if i[: -1] in data: # 前缀存在于data中，原始data为空，即先将单字母加入，依次进行加长判断
data.add(i) # 满足条件才加入
if len(i) > len(res) or (len(i) == len(res) and i < res): # 更新最长的字符串，或者相同长度更小的字符串
res = i
return res