• Leetcode 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]] += 1return anscnt = defaultdict(int)for s in arr:subs = get_substring(s)for k, v in subs.items():cnt[k] += vans = ["" 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。