472、连接词

leetcode

Created At : 2020-07-26 00:19

Count:551 Views 👀 :

Comment:

472、连接词
1. 示例:

题解

1、前缀树+dfs

472、连接词

给定一个不含重复单词的列表，编写一个程序，返回给定单词列表中所有的连接词。

连接词的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。

示例:

输入: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

输出: ["catsdogcats","dogcatsdog","ratcatdogcat"]

解释: "catsdogcats"由"cats", "dog" 和 "cats"组成; 
     "dogcatsdog"由"dog", "cats"和"dog"组成; 
     "ratcatdogcat"由"rat", "cat", "dog"和"cat"组成。

说明:

给定数组的元素总数不超过 10000。
给定数组中元素的长度总和不超过 600000。
所有输入字符串只包含小写字母。
不需要考虑答案输出的顺序。

链接：https://leetcode-cn.com/problems/concatenated-words

题解

1、前缀树+dfs

代码

// java
class Solution {
    // 前缀树数据结构
    class TrieNode{
        // 每一个对象内部含有26个子节点
        TrieNode[] children = new TrieNode[26];
        // 当前节点是否是一个单词
        boolean isWord = false;
    }

    // 根节点
    TrieNode node = new TrieNode();

    // 插入新的字符串
    public void insert(String s) {
        // 从跟开始
        TrieNode cur = node;
        for (int i = 0;i < s.length();i++) {
            int pos = s.charAt(i) - 'a';
            // 为子叶节点创建新的子叶节点
            if (cur.children[pos] == null) {
                cur.children[pos] = new TrieNode();
            }
            // 迭代遍历
            cur = cur.children[pos];
        }
        // 结尾节点true, 表示为单词
        cur.isWord = true;
    }

    List<String> res = new ArrayList<>();
    public List<String> findAllConcatenatedWordsInADict(String[] words) {
        if (words.length == 0) {
            return res;
        }
        // 将字符串插入前缀树
        for (String word: words) {
            if (word.length() != 0) {
                insert(word);
            }
        }
        // 深度优先查找
        for (String word:words) {
            if (dfs(word,node,0,0)) {
                res.add(word);
            }
        }
        return res;
    }

    private boolean dfs(String word, TrieNode cur, int count,int index) {
        for (int i = index;i < word.length();i++) {
            int pos = word.charAt(i) - 'a';
            // 遍历到叶子节点，直接返回
            if (cur.children[pos] == null) {
                return false;
            }
            cur = cur.children[pos];
            // 遍历到单词，继续向下遍历，仍有单词返回true
            if (cur.isWord && dfs(word,node,count + 1,i + 1)) {
                return true;
            }
        }

        return count > 0 && cur.isWord;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com