Medium
题目描述
给你一个由 n 个非空字符串组成的数组 arr。
请你构造一个长度为 n 的字符串数组 answer，满足：
answer[i]是arr[i]的最短子字符串，且该子字符串不会作为子字符串出现在数组中的其他字符串中。如果有多个这样的子字符串，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.length2 <= n <= 1001 <= arr[i].length <= 20arr[i]仅由小写英文字母组成
解题思路
这是一个典型的子字符串匹配问题，需要找到每个字符串中独有的最短子字符串。
解题思路：
暴力枚举法：对于每个字符串，我们需要枚举其所有可能的子字符串，从长度为1开始逐步增加长度。
哈希表优化：首先预处理所有字符串的所有子字符串，使用哈希表记录每个子字符串出现在哪些字符串中。
查找策略：对于当前字符串
arr[i]，按照子字符串长度从小到大的顺序遍历其所有子字符串。对于相同长度的子字符串，按照字典序从小到大遍历。判断条件：一个子字符串是有效的当且仅当它只出现在当前字符串中，不在其他任何字符串中出现。
算法步骤：
- 构建哈希表，记录所有子字符串及其出现的字符串索引
- 对于每个字符串，枚举其所有子字符串（按长度和字典序排序）
- 找到第一个只在当前字符串中出现的子字符串
- 如果找不到，返回空字符串
这种方法确保了找到的是最短且字典序最小的独有子字符串。
代码实现
class Solution {
public:
vector<string> shortestSubstrings(vector<string>& arr) {
int n = arr.size();
unordered_map<string, vector<int>> substringMap;
// 构建所有子字符串的映射
for (int i = 0; i < n; i++) {
string& s = arr[i];
unordered_set<string> seen;
for (int j = 0; j < s.length(); j++) {
for (int k = j; k < s.length(); k++) {
string sub = s.substr(j, k - j + 1);
if (seen.find(sub) == seen.end()) {
seen.insert(sub);
substringMap[sub].push_back(i);
}
}
}
}
vector<string> result(n);
for (int i = 0; i < n; i++) {
string& s = arr[i];
string answer = "";
// 按长度枚举子字符串
for (int len = 1; len <= s.length() && answer.empty(); len++) {
vector<string> candidates;
for (int j = 0; j <= s.length() - len; j++) {
string sub = s.substr(j, len);
if (substringMap[sub].size() == 1 && substringMap[sub][0] == i) {
candidates.push_back(sub);
}
}
if (!candidates.empty()) {
sort(candidates.begin(), candidates.end());
answer = candidates[0];
}
}
result[i] = answer;
}
return result;
}
};
class Solution:
def shortestSubstrings(self, arr: List[str]) -> List[str]:
n = len(arr)
substring_map = {}
# 构建所有子字符串的映射
for i in range(n):
s = arr[i]
seen = set()
for j in range(len(s)):
for k in range(j, len(s)):
sub = s[j:k+1]
if sub not in seen:
seen.add(sub)
if sub not in substring_map:
substring_map[sub] = []
substring_map[sub].append(i)
result = []
for i in range(n):
s = arr[i]
answer = ""
# 按长度枚举子字符串
for length in range(1, len(s) + 1):
if answer:
break
candidates = []
for j in range(len(s) - length + 1):
sub = s[j:j+length]
if len(substring_map[sub]) == 1 and substring_map[sub][0] == i:
candidates.append(sub)
if candidates:
candidates.sort()
answer = candidates[0]
result.append(answer)
return result
public class Solution {
public string[] ShortestSubstrings(string[] arr) {
int n = arr.Length;
var substringMap = new Dictionary<string, List<int>>();
// 构建所有子字符串的映射
for (int i = 0; i < n; i++) {
string s = arr[i];
var seen = new HashSet<string>();
for (int j = 0; j < s.Length; j++) {
for (int k = j; k < s.Length; k++) {
string sub = s.Substring(j, k - j + 1);
if (!seen.Contains(sub)) {
seen.Add(sub);
if (!substringMap.ContainsKey(sub)) {
substringMap[sub] = new List<int>();
}
substringMap[sub].Add(i);
}
}
}
}
string[] result = new string[n];
for (int i = 0; i < n; i++) {
string s = arr[i];
string answer = "";
// 按长度枚举子字符串
for (int len = 1; len <= s.Length && string.IsNullOrEmpty(answer); len++) {
var candidates = new List<string>();
for (int j = 0; j <= s.Length - len; j++) {
string sub = s.Substring(j, len);
if (substringMap[sub].Count == 1 && substringMap[sub][0] == i) {
candidates.Add(sub);
}
}
if (candidates.Count > 0) {
candidates.Sort();
answer = candidates[0];
}
}
result[i] = answer;
}
return result;
}
}
var shortestSubstrings = function(arr) {
const n = arr.length;
const result = new Array(n).fill("");
for (let i = 0; i < n; i++) {
const str = arr[i];
let minLen = Infinity;
let candidate = "";
// Generate all substrings of str
for (let start = 0; start < str.length; start++) {
for (let end = start + 1; end <= str.length; end++) {
const substr = str.substring(start, end);
// Check if this substring appears in any other string
let found = false;
for (let j = 0; j < n; j++) {
if (j !== i && arr[j].includes(substr)) {
found = true;
break;
}
}
// If not found in other strings, it's a candidate
if (!found) {
if (substr.length < minLen ||
(substr.length === minLen && substr < candidate)) {
minLen = substr.length;
candidate = substr;
}
}
}
}
result[i] = candidate;
}
return result;
};
复杂度分析
| 复杂度类型 | 复杂度 |
|---|---|
| 时间复杂度 | O(n × L³) |
| 空间复杂度 | O(n × L²) |
其中 n 是字符串数组的长度，L 是字符串的平均长度。时间复杂度主要来自于枚举所有子字符串（O(L²)）和字符串操作（O(L)），空间复杂度来自于存储所有子字符串的哈希表。