class Solution {
public:
vector<string> shortestSubstrings(vector<string>& arr) {
}
};
3076. 数组中的最短非公共子字符串
给你一个数组 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.length2 <= n <= 1001 <= arr[i].length <= 20arr[i] 只包含小写英文字母。原站题解
golang 解法, 执行用时: 20 ms, 内存消耗: 3.7 MB, 提交时间: 2024-03-13 20:08:04
func shortestSubstrings(arr []string) []string {
ans := make([]string, len(arr))
for i, s := range arr {
m := len(s)
res := ""
for size := 1; size <= m && res == ""; size++ {
next:
for k := size; k <= m; k++ {
sub := s[k-size : k]
if res != "" && sub >= res {
continue
}
for j, t := range arr {
if j != i && strings.Contains(t, sub) {
continue next
}
}
res = sub
}
}
ans[i] = res
}
return ans
}
cpp 解法, 执行用时: 62 ms, 内存消耗: 25.4 MB, 提交时间: 2024-03-13 20:07:45
class Solution {
public:
vector<string> shortestSubstrings(vector<string> &arr) {
int n = arr.size();
auto check = [&](int i, string &sub) {
for (int j = 0; j < n; j++) {
if (j != i && arr[j].find(sub) != string::npos) {
return false;
}
}
return true;
};
vector<string> ans(n);
for (int i = 0; i < n; i++) {
int m = arr[i].size();
string res;
for (int size = 1; size <= m && res.empty(); size++) {
for (int j = size; j <= m; j++) {
string t = arr[i].substr(j - size, size);
if ((res.empty() || t < res) && check(i, t)) {
res = t;
}
}
}
ans[i] = res;
}
return ans;
}
};
java 解法, 执行用时: 44 ms, 内存消耗: 44.4 MB, 提交时间: 2024-03-13 20:07:32
class Solution {
public String[] shortestSubstrings(String[] arr) {
int n = arr.length;
String[] ans = new String[n];
for (int i = 0; i < n; i++) {
int m = arr[i].length();
String res = "";
for (int size = 1; size <= m && res.isEmpty(); size++) {
for (int j = size; j <= m; j++) {
String t = arr[i].substring(j - size, j);
if ((res.isEmpty() || t.compareTo(res) < 0) && check(arr, i, t)) {
res = t;
}
}
}
ans[i] = res;
}
return ans;
}
private boolean check(String[] arr, int i, String sub) {
for (int j = 0; j < arr.length; j++) {
if (j != i && arr[j].contains(sub)) {
return false;
}
}
return true;
}
}
python3 解法, 执行用时: 148 ms, 内存消耗: 16.3 MB, 提交时间: 2024-03-13 20:07:18
class Solution:
def shortestSubstrings(self, arr: List[str]) -> List[str]:
def check(i: int, sub: str) -> bool:
for j, s in enumerate(arr):
if j != i and sub in s:
return False
return True
ans = []
for i, s in enumerate(arr):
m = len(s)
res = ""
for size in range(1, m + 1):
for j in range(size, m + 1):
t = s[j - size: j]
if (not res or t < res) and check(i, t):
res = t
if res: break
ans.append(res)
return ans