Leetcode 1408:数组中的字符串匹配(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1408:数组中的字符串匹配(超详细的解法!!!)

in leetcode with 0 comment

给你一个字符串数组 words ,数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。

如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ,那么字符串 words[i] 就是 words[j] 的一个子字符串。

示例 1:

输入:words = ["mass","as","hero","superhero"]
输出:["as","hero"]
解释:"as" 是 "mass" 的子字符串,"hero" 是 "superhero" 的子字符串。
["hero","as"] 也是有效的答案。

示例 2:

输入:words = ["leetcode","et","code"]
输出:["et","code"]
解释:"et" 和 "code" 都是 "leetcode" 的子字符串。

示例 3:

输入:words = ["blue","green","bu"]
输出:[]

提示:

解题思路

首先不难想到暴力解法,枚举所有的字符串对,判断其中一个是不是另外一个的子串,需要注意重复子串的问题,这里采用了最暴力的做法通过set存储。

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        res = set()
        n = len(words)
        for i in range(n):
            for j in range(n):
                if i != j and words[i].find(words[j]) != -1:
                    res.add(words[j])
        return list(res)

那么这种做法的时间复杂度就是O(N^2*S^2),其中N表示单词的个数,S表示最长字符串的长度。也可以通过排序来处理判重问题,将长度较短的字符排在前面,然后从前向后遍历,判断当前这个较短的字符串是不是后面较长字符串的子串即可。

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        words.sort(key=len)
        n, res = len(words), []
        
        for i in range(n):
            for j in range(i + 1, n):
                if words[j].find(words[i]) != -1:
                    res.append(words[i])
                    break
        return res

还有一个更加简洁的做法,我们将words中的字符串串联成sen,如果words中的一个单词s是另外一个单词t的子串话,那么单词s一定在sen中至少出现两次。

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        sen = ' '.join(words)
        return [i for i in words if sen.count(i) >= 2]

这种做法的时间复杂度和前面是一样的。

这个问题其实满足了Trie)的性质,我们可以使用Trie处理这个问题,可以将每个单词的后缀存储于Trie中,然后判断每个单词是不是在Trie中出现过即可。最后就是判重的问题,当然可以采用排序的处理思路,但是我们这里通过在Trie中的添加计数节点'#'记录单词中的字符出现次数。如果一个字符串在Trie中出现,并且它的结尾字符出现超过1次,那么它就是符合条件的。

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        def add(word):
            node = root
            for c in word:
                node = node[c]
                node['#'] = node.get('#', 0) + 1

        def get(word):
            node = root
            for c in word:
                if (node := node.get(c)) is None: return False
            return node['#'] > 1

        Trie = lambda: collections.defaultdict(Trie)
        root = Trie()
        for word in words:
            for i in range(len(word)):
                add(word[i:])
        return [word for word in words if get(word)]

reference:

https://leetcode.com/problems/string-matching-in-an-array/discuss/577564/Python3-Simple-Code

https://leetcode.com/problems/string-matching-in-an-array/discuss/575147/Clean-Python-3-suffix-trie-O(NlogN-%2B-N-*-S2)

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses