小工具知识网

当前位置: 首页 > 行业知识 > Leetcode 3076. Shortest Uncommon Substring in an Array

行业知识

Leetcode 3076. Shortest Uncommon Substring in an Array

2026-11-17 13:39:31 来源:互联网转载
  • Leetcoindex.php/tags-41973.html" >de 3076. Shortest Uncommon Substring in an Array
    • 1. 解题思路
    • 2. 代码实现
      • 题目链接:3076. Shortest Uncommon Substring in an Array

        1. 解题思路

        这一题我的思路上很暴力,就是直接把所有可能的substring全部统计出来放到一起。

        ()

        然后,对于每一个string,我们考察其substring当中哪些部分的count和总的count是一样的,那么它们就是只出现在这个单词当中的,此时,我们就能够快速获得每一个string中满足条件的substring了,然后,我们将其按照题目条件选择最短的那个返回即可。

        2. 代码实现

        给出python代码实现如下:

        ()
        class Solution:    def shortestSubstrings(self, arr: List[str]) -> List[str]:                @lru_cache(None)        def get_substring(s):            n = len(s)            ans = defaultdict(int)            for i in range(n):                for j in range(i+1, n+1):                    ans[s[i:j]] += 1            return ans                cnt = defaultdict(int)        for s in arr:            subs = get_substring(s)            for k, v in subs.items():                cnt[k] += v        ans = ["" for _ in arr]        for i, s in enumerate(arr):            subs = get_substring(s)            valid = sorted([k for k in subs if subs[k] == cnt[k]], key=lambda x: (len(x), x))            if valid != []:                ans[i] = valid[0]        return ans

        提交代码评测得到:耗时246ms,占用内存17.5MB。

上一篇:父母的车怎么备案给儿子上牌照

下一篇:电脑怎么暂停重置服务器?