列表

详情

472. 连接词

给你一个 不含重复 单词的字符串数组 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"]

 

提示：

相似题目

单词拆分 II

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<string> findAllConcatenatedWordsInADict(vector<string>& words) { } };

php 解法, 执行用时: 288 ms, 内存消耗: 37.9 MB, 提交时间: 2023-10-09 10:39:02 

class Solution {
    /**
     * @param String[] $words
     * @return String[]
     */
    function findAllConcatenatedWordsInADict($words) {
        $this->root = new TrieNode();
        uasort($words, [$this, 'sortByLength']);
        $ret = [];
        foreach ($words as $word) {
            if(strlen($word)==0){
                continue;
            }elseif ($this->helper($word)) {
                array_push($ret, $word);
            }else{
                $this->addWord($word);
            }
        }
        return $ret;
    }

    function sortByLength($a,$b) {
        return strlen($a) - strlen($b);
    }

    function helper($word) {
        if(strlen($word)==0) return true;
        $tree = $this->root;
        for ($i=0; $i < strlen($word); $i++) { 
            $c = $word[$i];
            $tree = $tree->next[$c];
            if(!$tree){
                return false;
            }
            if($tree->isWord){
                if($this->helper(substr($word, $i+1))){
                    return true;
                }
            }
        }
        return false;
    }

    function addWord($word) {
        $tree = $this->root;
        for ($i=0; $i < strlen($word); $i++) { 
            $c = $word[$i];
            if(!isset($tree->next[$c])){
                $tree->next[$c] = new TrieNode();
            }
            $tree = $tree->next[$c];
        }
        if(!$tree->isWord){
            $tree->isWord = true;
        }
    }
}

// 字典树
class TrieNode {
    public $isWord = false;
    public $next = [];
}

python3 解法, 执行用时: 348 ms, 内存消耗: 27.4 MB, 提交时间: 2023-10-09 10:37:28 

class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        def helper(word: str, root: dict) -> bool:
            if len(word) == 0:
                return True
            tree = root
            for i,c in enumerate(word):
                tree = tree.get(c, None)
                if not tree:
                    return False
                if '#' in tree:
                    if helper(word[i+1:], root):
                        return True
            return False
        
        def addWord(word: str) -> None:
            tree = root
            for c in word:
                if c not in tree:
                    tree[c] = {}
                tree = tree[c]
            tree['#'] = {}
            
        words.sort(key=lambda x: len(x))
        ret = []
        root = {}
        for word in words:
            if len(word)==0:
                continue
            if helper(word, root):
                ret.append(word)
            else:
                addWord(word)
        return ret

javascript 解法, 执行用时: 256 ms, 内存消耗: 73.4 MB, 提交时间: 2023-10-09 10:35:00 

/**
 * @param {string[]} words
 * @return {string[]}
 */
var findAllConcatenatedWordsInADict = function(words) {
    const root = new Trie(), ans = [];
    words.sort((a,b)=>(a.length - b.length));
    for(const word of words){
        if(word.length == 0)
            continue;
        if(root.find(root, word))
            ans.push(word);
        else
            root.insert(word);
    }
    return ans;
};

class Trie{
    constructor(){
        this.children = new Array(26);
        this.isEnd = false;
    }

    insert(word){
        let node = this;
        for(let i=0;i<word.length;i++){
            const idx = word.charCodeAt(i) - 'a'.charCodeAt(0);
            if(node.children[idx] === undefined)
                node.children[idx] = new Trie();
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    find(root, word){
        let node = root;
        for(let i=0;i<word.length;i++){
            if(node.isEnd)
                if(this.find(root, word.substring(i, word.length)))
                    return true;
            const idx = word.charCodeAt(i) - 'a'.charCodeAt(0);
            if(node.children[idx] === undefined)
                return false;
            node = node.children[idx];
        }
        return node.isEnd;
    }
}

java 解法, 执行用时: 37 ms, 内存消耗: 57.9 MB, 提交时间: 2023-10-09 10:33:24 

class Solution {
    Trie trie = new Trie();

    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        List<String> ans = new ArrayList<String>();
        Arrays.sort(words, (a, b) -> a.length() - b.length());
        for (int i = 0; i < words.length; i++) {
            String word = words[i];
            if (word.length() == 0) {
                continue;
            }
            boolean[] visited = new boolean[word.length()];
            if (dfs(word, 0, visited)) {
                ans.add(word);
            } else {
                insert(word);
            }
        }
        return ans;
    }

    public boolean dfs(String word, int start, boolean[] visited) {
        if (word.length() == start) {
            return true;
        }
        if (visited[start]) {
            return false;
        }
        visited[start] = true;
        Trie node = trie;
        for (int i = start; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            node = node.children[index];
            if (node == null) {
                return false;
            }
            if (node.isEnd) {
                if (dfs(word, i + 1, visited)) {
                    return true;
                }
            }
        }
        return false;
    }
    
    public void insert(String word) {
        Trie node = trie;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
}

class Trie {
    Trie[] children;
    boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
}

cpp 解法, 执行用时: 340 ms, 内存消耗: 255.1 MB, 提交时间: 2023-10-09 10:32:48 

struct Trie {
    bool isEnd;
    vector<Trie *> children;
    Trie() {
        this->children = vector<Trie *>(26, nullptr);
        this->isEnd = false;
    }
};

class Solution {
public:
    Trie * trie = new Trie();

    vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
        vector<string> ans;
        sort(words.begin(), words.end(), [&](const string & a, const string & b){
            return a.size() < b.size(); 
        });
        for (int i = 0; i < words.size(); i++) {
            string word = words[i];
            if (word.size() == 0) {
                continue;
            }
            vector<int> visited(word.size(), 0);
            if (dfs(word, 0, visited)) {
                ans.emplace_back(word);
            } else {
                insert(word);
            }
        }
        return ans;
    }

    bool dfs(const string & word, int start, vector<int> & visited) {
        if (word.size() == start) {
            return true;
        }
        if (visited[start]) {
            return false;
        }
        visited[start] = true;
        Trie * node = trie;
        for (int i = start; i < word.size(); i++) {
            char ch = word[i];
            int index = ch - 'a';
            node = node->children[index];
            if (node == nullptr) {
                return false;
            }
            if (node->isEnd) {
                if (dfs(word, i + 1, visited)) {
                    return true;
                }
            }
        }
        return false;
    }

    void insert(const string & word) {
        Trie * node = trie;
        for (int i = 0; i < word.size(); i++) {
            char ch = word[i];
            int index = ch - 'a';
            if (node->children[index] == nullptr) {
                node->children[index] = new Trie();
            }
            node = node->children[index];
        }
        node->isEnd = true;
    }
};

golang 解法, 执行用时: 92 ms, 内存消耗: 53.6 MB, 提交时间: 2023-10-09 10:32:30 

type trie struct {
    children [26]*trie
    isEnd    bool
}

func (root *trie) insert(word string) {
    node := root
    for _, ch := range word {
        ch -= 'a'
        if node.children[ch] == nil {
            node.children[ch] = &trie{}
        }
        node = node.children[ch]
    }
    node.isEnd = true
}

func (root *trie) dfs(vis []bool, word string) bool {
    if word == "" {
        return true
    }
    if vis[len(word)-1] {
        return false
    }
    vis[len(word)-1] = true
    node := root
    for i, ch := range word {
        node = node.children[ch-'a']
        if node == nil {
            return false
        }
        if node.isEnd && root.dfs(vis, word[i+1:]) {
            return true
        }
    }
    return false
}

func findAllConcatenatedWordsInADict(words []string) (ans []string) {
    sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })

    root := &trie{}
    for _, word := range words {
        if word == "" {
            continue
        }
        vis := make([]bool, len(word))
        if root.dfs(vis, word) {
            ans = append(ans, word)
        } else {
            root.insert(word)
        }
    }
    return
}

python3 解法, 执行用时: 816 ms, 内存消耗: 34.1 MB, 提交时间: 2023-10-09 10:32:04 

class Trie:
    def __init__(self):
        self.children = [None] * 26
        self.isEnd = False

    def insert(self, word: str):
        node = self
        for ch in word:
            ch = ord(ch) - ord('a')
            if not node.children[ch]:
                node.children[ch] = Trie()
            node = node.children[ch]
        node.isEnd = True

    def dfs(self, word: str, start: int, vis: List[bool]) -> bool:
        if start == len(word):
            return True
        if vis[start]:
            return False
        vis[start] = True
        node = self
        for i in range(start, len(word)):
            node = node.children[ord(word[i]) - ord('a')]
            if node is None:
                return False
            if node.isEnd and self.dfs(word, i + 1, vis):
                return True
        return False


'''
字典树 + dfs
'''
class Solution:
    def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]:
        words.sort(key=len)

        ans = []
        root = Trie()
        for word in words:
            if word == "":
                continue
            if root.dfs(word, 0, [False] * len(word)):
                ans.append(word)
            else:
                root.insert(word)
        return ans

上一题

© 2024 leetcode.cn