3076. Shortest Uncommon Substring in an Array

You are given an array arr of size n consisting of non-empty strings.

Find a string array answer of size n such that:

• answer[i] is the shortest substring of arr[i] that does not occur as a substring in any other string in arr. If multiple such substrings exist, answer[i] should be the lexicographically smallest. And if no such substring exists, answer[i] should be an empty string.

Return the array answer.

Example 1:

Input: arr = ["cab","ad","bad","c"]
Output: ["ab","","ba",""]
Explanation: We have the following:
- For the string "cab", the shortest substring that does not occur in any other string is either "ca" or "ab", we choose the lexicographically smaller substring, which is "ab".
- For the string "ad", there is no substring that does not occur in any other string.
- For the string "bad", the shortest substring that does not occur in any other string is "ba".
- For the string "c", there is no substring that does not occur in any other string.

Example 2:

Input: arr = ["abc","bcd","abcd"]
Output: ["","","abcd"]
Explanation: We have the following:
- For the string "abc", there is no substring that does not occur in any other string.
- For the string "bcd", there is no substring that does not occur in any other string.
- For the string "abcd", the shortest substring that does not occur in any other string is "abcd".

Constraints:

• n == arr.length

• 2 <= n <= 100

• 1 <= arr[i].length <= 20

• arr[i] consists only of lowercase English letters.

分析

1. Substring Generation: We first generate all possible substrings for each string in the input array and count how many times each substring appears across all strings using a dictionary.

2. Unique Substring Identification: For each string, we then check all possible substrings (starting from the shortest length) to find those that appear exactly once in our count dictionary (meaning they're unique to that string).

3. Result Selection: For each string, we select the lexicographically smallest substring among the shortest unique substrings found. If no unique substring exists, we return an empty string for that position.

```python3
class Solution:
    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        res = []
        count = defaultdict(int)
        for s in arr:
            subs = set()
            n = len(s)
            for i in range(n):
                for j in range(i+1,n+1):
                    subs.add(s[i:j])
            for i in subs:
                count[i]+=1

        for s in arr:
            unique_subs = []
            length = len(s)
            # Generate all possible substrings for current string
            # 第二轮从长度最短的开始 这样可以满足条件
            for l in range(1, length + 1):
                current_subs = set()
                for i in range(length - l + 1):
                    sub = s[i:i+l]
                    if count[sub] == 1:
                        current_subs.add(sub)
                if current_subs:
                    unique_subs.append(min(current_subs))
                    break  # Since we're checking increasing lengths, first valid is shortest
            if unique_subs:
                res.append(unique_subs[0])
            else:
                res.append("")
            
        return res
                
                
                

        
```