数组中的最短非公共子字符串

标签: 字典树 数组 哈希表 字符串

难度: Medium

给你一个数组 arr ，数组中有 n 个 非空 字符串。

请你求出一个长度为 n 的字符串 answer ，满足：

  • answer[i] 是 arr[i] 最短 的子字符串，且它不是 arr 中其他任何字符串的子字符串。如果有多个这样的子字符串存在，answer[i] 应该是它们中字典序最小的一个。如果不存在这样的子字符串，answer[i] 为空字符串。

请你返回数组 answer 。

示例 1：

输入：arr = ["cab","ad","bad","c"]
输出：["ab","","ba",""]
解释：求解过程如下：
- 对于字符串 "cab" ，最短没有在其他字符串中出现过的子字符串是 "ca" 或者 "ab" ，我们选择字典序更小的子字符串，也就是 "ab" 。
- 对于字符串 "ad" ，不存在没有在其他字符串中出现过的子字符串。
- 对于字符串 "bad" ，最短没有在其他字符串中出现过的子字符串是 "ba" 。
- 对于字符串 "c" ，不存在没有在其他字符串中出现过的子字符串。

示例 2：

输入：arr = ["abc","bcd","abcd"]
输出：["","","abcd"]
解释：求解过程如下：
- 对于字符串 "abc" ，不存在没有在其他字符串中出现过的子字符串。
- 对于字符串 "bcd" ，不存在没有在其他字符串中出现过的子字符串。
- 对于字符串 "abcd" ，最短没有在其他字符串中出现过的子字符串是 "abcd" 。

提示：

  • n == arr.length
  • 2 <= n <= 100
  • 1 <= arr[i].length <= 20
  • arr[i] 只包含小写英文字母。

Submission

运行时间: 125 ms

内存: 16.7 MB

class Solution:
    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        ### solution 2:
        hh = dict()
        has_sub = set()
        ans = [""]*len(arr)
        for ind,each in enumerate(arr):
            for i in range(0, len(each)):
                for j in range(i+1, len(each)+1):
                    sub_i_j = each[i:j]

                    if sub_i_j in has_sub:
                        continue
                    
                    if sub_i_j in hh:
                        if hh[sub_i_j] != ind:
                            del hh[sub_i_j]
                            has_sub.add(sub_i_j)
                    else:
                        hh[sub_i_j]  = ind

        for k,v in hh.items():
            if not (ans[v]):
                ans[v] = k
            else:
                if len(k) < len(ans[v]):
                    ans[v] = k
                elif len(k) == len(ans[v]):
                    ans[v] = min(ans[v], k)
        
        return ans
        
        
        
        
        
        
        
        
        ### solution 1: 字典：每个string -> 自己的substring
        # hh = dict()
        # ans = [""]*len(arr)
        # for each in arr:
        #     hh[each] = set()
        #     for i in range(0, len(each)):
        #         for j in range(i+1, len(each)+1):
        #             hh[each].add(each[i:j])
        # for i,each_i in enumerate(arr):
        #     cur = hh[each_i]
        #     for j,each_j in enumerate(arr):
        #         if i==j:
        #             continue
        #         cur = cur - hh[each_j]
        #     if cur:
        #         min_sub = list(cur)[0]
        #         min_l = len(min_sub)
        #         for each_unique_sub in cur:
        #             if len(each_unique_sub) < min_l:
        #                 min_l = len(each_unique_sub)
        #                 min_sub = each_unique_sub
        #             elif len(each_unique_sub) == min_l:
        #                 min_sub = min(min_sub, each_unique_sub)
        #         ans[i] = min_sub
        # return ans

Explain

此题解采用了一种有效的方法来查找每个字符串中最短的、不是其他任何字符串子串的子字符串。方法包括创建一个哈希表来存储每个子字符串及其所属的原始字符串索引。对于数组中的每个字符串，生成所有可能的子字符串，并使用哈希表记录它们。如果一个子字符串已经存在且来自不同的字符串，则标记为公共子串。遍历完所有字符串后，再次检查哈希表中记录的子字符串，为每个字符串选择最短且字典序最小的非公共子字符串。

时间复杂度: O(n * L^2)

空间复杂度: O(n * L^2)

class Solution:
    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        hh = dict()  # 存储子字符串及其原始字符串的索引
        has_sub = set()  # 存储被标记为公共的子字符串
        ans = ['']*len(arr)  # 初始化答案数组
        for ind, each in enumerate(arr):  # 遍历每个字符串
            for i in range(len(each)):
                for j in range(i+1, len(each)+1):
                    sub_i_j = each[i:j]  # 生成子字符串
                    if sub_i_j in has_sub:  # 如果已标记为公共，则跳过
                        continue
                    if sub_i_j in hh:  # 检查子字符串是否已存在
                        if hh[sub_i_j] != ind:  # 来自不同字符串
                            del hh[sub_i_j]  # 删除，因为它是公共的
                            has_sub.add(sub_i_j)  # 添加到公共集合
                    else:
                        hh[sub_i_j] = ind  # 记录子字符串的来源
        for k, v in hh.items():  # 选取每个字符串的最短且字典序最小的非公共子字符串
            if not ans[v]:  # 如果还没有找到答案
                ans[v] = k
            else:  # 比较长度和字典序
                if len(k) < len(ans[v]):
                    ans[v] = k  # 更新更短的子字符串
                elif len(k) == len(ans[v]):
                    ans[v] = min(ans[v], k)  # 更新字典序更小的
        return ans  # 返回结果

Explore

在这个问题中，目标是找到每个字符串中最短的、不是其他字符串的子串的子字符串。若只添加特定长度的子字符串到哈希表，可能会遗漏可能的最短非公共子字符串。例如，如果仅考虑长度为3的子字符串，可能错过长度为2或更短的有效非公共子字符串。因此，添加所有可能的子字符串到哈希表可以确保不遗漏任何潜在的最短非公共子字符串。

在处理过程中，当我们遇到一个新的子字符串时，首先检查它是否已经存在于哈希表中。如果已存在，并且现有记录的来源字符串索引与当前字符串的索引不同，这表明此子字符串至少出现在两个不同的字符串中，因而是一个公共子串。此时，我们将该子字符串从哈希表中删除，并将其添加到一个集合中，用于标记已知的公共子字符串。这样的处理确保了任何被多次发现的子字符串都不会被考虑为答案的一部分。

在最后的选择阶段，对于哈希表中剩余的每个非公共子字符串，我们检查其长度和字典序以确定是否更新当前字符串的结果。首先，我们检查是否已经为当前字符串找到一个非公共子字符串。如果未找到或找到的子字符串比当前子字符串长，我们则更新答案为当前子字符串。如果长度相同，我们比较并选择字典序较小的子字符串。这个过程确保了对于每个字符串，我们都选取了最短的，并在长度相同的情况下选择字典序最小的非公共子字符串，从而达到全局最优。