python3 解法, 执行用时: 60 ms, 内存消耗: 21.3 MB, 提交时间: 2022-11-30 22:28:55

class Solution:
    def longestWord(self, words: List[str]) -> str:
        from collections import defaultdict
        from functools import reduce
        Trie = lambda: defaultdict(Trie)
        trie = Trie()
        END = True
        for i, word in enumerate(words):
            if word:  # 非常重要，当含有空串的时候非常麻烦
                reduce(dict.__getitem__, word, trie)[END] = i
        def dfs(s: str, idx: int, word_cnt: int, tree: Trie) -> bool:
            """暴力搜索Trie，当前是单词节点，可选择或不选择"""
            if len(s) == idx:
                return word_cnt >= 1 and END in tree
            # 存在节点，比如 cat,cats 的选择，若选择则从头查找，不选择继续向下
            if END in tree:
                if dfs(s, idx, word_cnt + 1, trie):  
                    return True
            # 下面这行一定要在上面之后，因为判断节点 s[idx] 是下一个单词。若在前面则 return False
            if s[idx] not in tree:
                return False
            if dfs(s, idx + 1, word_cnt, tree[s[idx]]):
                return True
            return False
            # return s[idx] in tree and dfs(s, idx + 1, word_cnt, tree[s[idx]])
        # 对所有单词进行暴力搜索
        res = ''
        for word in words:
            if dfs(word, 0, 0, trie) and \
            (len(word) > len(res) or (len(word) == len(res) and res > word)):
                res = word
        return res

python3 解法, 执行用时: 44 ms, 内存消耗: 15.2 MB, 提交时间: 2022-11-30 22:28:28

class Solution:
    def longestWord(self, words: List[str]) -> str:
        d = set(words)

        def dfs(word: str, idx: int, wordCnt: int) -> bool:
            """枚举当前单词连接子串，查询字典 d 进行爆搜"""
            if idx >= len(word):
                return wordCnt > 1
            for i in range(idx, len(word)):
                substr = word[idx:i+1]
                if substr in d and dfs(word, i + 1, wordCnt + 1):  # 可重复用
                    return True
            return False

        # 1.先逆序排序：(长度，字典序)，然后对所有单词进行暴力搜索
        words.sort(key=lambda x: (-len(x), x))
        for word in words:
            if dfs(word, 0, 0):  # 第一次找到肯定是答案
                return word
        return ''

javascript 解法, 执行用时: 104 ms, 内存消耗: 47.4 MB, 提交时间: 2022-11-30 22:27:37

/**
 * @param {string[]} words
 * @return {string}
 */
var longestWord = function(words) {
    words.sort((a,b)=>{
        if(a.length === b.length){
            return a < b ? -1 : 1
        }else{
            return a.length > b.length? -1 : 1
        }
    })

    for(let sentence of words) {
        const length = sentence.length;
        const dp = new Array(length+1).fill(0);
        for(let i=1; i<=length; i++) {
            dp[i] = dp[i-1]+1;
            for(let word of words){
                const len = word.length;
                if(sentence !== word && length>len && sentence.slice(i-len,i) === word){
                    dp[i] = Math.min(dp[i],dp[i-len])
                }
            }
        }
        if(dp[length] === 0 ) return sentence;
        
    }
    return '';
};

python3 解法, 执行用时: 80 ms, 内存消耗: 15 MB, 提交时间: 2022-11-30 22:26:59

class Solution:
    def longestWord(self, words: List[str]) -> str:
        def f(word):
            for i in range(len(word)):
                left = word[:i]
                right = word[i:]
                if left in words:  # 如果单词的左边是组合中的一个单词，则继续看右边
                    if right in words:
                        return True
                    elif f(right):  # 如果单词的右边是其他单词的组合，则返回 ture。否则继续寻找下一种划分。
                        return True
                    else:
                        continue
                else:
                    continue  # 如果单词的左边不是组合中的一个单词，则进行下一种划分。
            return False  # 如果不存在任何正确的划分，返回 false。
        res = ''
        for word in words:
            if f(word):
                if len(word) > len(res):
                    res = word
                elif len(word) == len(res):
                    res = min(res, word)
        return res

java 解法, 执行用时: 4 ms, 内存消耗: 40.8 MB, 提交时间: 2022-11-30 22:24:48

class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words,(o1,o2)->{
            if(o1.length() == o2.length())
                return o1.compareTo(o2);
            else{
                return Integer.compare(o2.length(),o1.length());
            }
        });

        Set<String> set = new HashSet<>(Arrays.asList(words));
        for(String word : words){
            set.remove(word);
            if(find(set,word))
                 return word;
        }
        return "";
    }

    public boolean find(Set<String> set, String word){
        if(word.length() == 0)
            return true;
        for(int i = 0; i < word.length(); i++){
            if(set.contains(word.substring(0,i+1)) && find(set,word.substring(i+1)))
                return true;
        }
        return false;
    }
}