What is the Shortest Uncommon Substring in an Array problem pattern?

It follows array scanning plus hash lookup, identifying minimal substrings unique to each string.

How do I handle strings with no unique substring?

Return an empty string for any string where every substring appears in another string.

Is lexicographical order important when multiple substrings qualify?

Yes, always return the lexicographically smallest substring to match problem requirements.

Can this problem be solved with a trie?

Yes, a trie can store all substrings and help find the shortest unique substring efficiently.

What is the expected complexity of a hash-based approach?

Using hash maps to count substrings reduces time complexity to O(n * l^2) and space complexity depends on total substring storage.

#3076

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个数组 arr ，数组中有 n 个非空字符串。请你求出一个长度为 n 的字符串数组 answer ，满足： answer[i] 是 arr[i] 最短的子字符串，且它不是 arr 中其他任何字符串的子字符串。如果有多个这样的子字符串存在， answer[i] 应该是它们中字典序最小的一…

数组哈希表字符串字典树

题目描述

给你一个数组 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] 只包含小写英文字母。

lightbulb

解题思路

方法一：枚举

我们注意到数据规模很小，所以可以直接枚举每个字符串的所有子串，然后判断是否是其他字符串的子串。

具体地，我们先枚举每个字符串 arr[i]，然后从小到大枚举每个子串的长度 $j$ ，然后枚举每个子串的起始位置 $l$ ，可以得到当前子串为 sub = arr[i][l:l+j]，然后判断 sub 是否是其他字符串的子串，如果是的话，就跳过当前子串，否则更新答案。

时间复杂度 $O(n^2 \times m^4)$ ，空间复杂度 $O(m)$ 。其中 $n$ 是字符串数组 arr 的长度，而 $m$ 是字符串的最大长度，本题中 $m \le 20$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        ans = [""] * len(arr)
        for i, s in enumerate(arr):
            m = len(s)
            for j in range(1, m + 1):
                for l in range(m - j + 1):
                    sub = s[l : l + j]
                    if not ans[i] or ans[i] > sub:
                        if all(k == i or sub not in t for k, t in enumerate(arr)):
                            ans[i] = sub
                if ans[i]:
                    break
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on substring generation and checking; brute force can be O(n * l^3), trie optimization reduces repeated checks, and hash maps reduce to O(n * l^2) where l is string length. Space complexity ranges from O(n * l^2) for hash storage to potentially larger for trie structures.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Looking for correct handling of overlapping substrings across multiple strings.
question_mark
Checking for efficient substring uniqueness detection using hash tables or tries.
question_mark
Expect candidate to consider lexicographical ordering when multiple minimal substrings exist.

warning

常见陷阱

外企场景

error
Failing to consider all possible substrings including single characters.
error
Not returning empty string when no unique substring exists.
error
Ignoring lexicographical order when multiple minimal substrings are valid.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find the shortest uncommon prefix instead of any substring.
arrow_right_alt
Return the longest unique substring instead of shortest.
arrow_right_alt
Handle arrays with duplicate strings efficiently.

help

常见问题

外企场景

继续练习

#3043 最长公共前缀的长度 #2707 字符串中的额外字符 #2227 加密解密字符串