Question

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

English Version

题目描述

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

解法

方法一：枚举

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

具体地，我们先枚举每个字符串 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$。

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

class Solution {
  public String[] shortestSubstrings(String[] arr) {
    int n = arr.length;
    String[] ans = new String[n];
    Arrays.fill(ans, "");
    for (int i = 0; i < n; ++i) {
      int m = arr[i].length();
      for (int j = 1; j <= m && ans[i].isEmpty(); ++j) {
        for (int l = 0; l <= m - j; ++l) {
          String sub = arr[i].substring(l, l + j);
          if (ans[i].isEmpty() || sub.compareTo(ans[i]) < 0) {
            boolean ok = true;
            for (int k = 0; k < n && ok; ++k) {
              if (k != i && arr[k].contains(sub)) {
                ok = false;
              }
            }
            if (ok) {
              ans[i] = sub;
            }
          }
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  vector<string> shortestSubstrings(vector<string>& arr) {
    int n = arr.size();
    vector<string> ans(n);
    for (int i = 0; i < n; ++i) {
      int m = arr[i].size();
      for (int j = 1; j <= m && ans[i].empty(); ++j) {
        for (int l = 0; l <= m - j; ++l) {
          string sub = arr[i].substr(l, j);
          if (ans[i].empty() || sub < ans[i]) {
            bool ok = true;
            for (int k = 0; k < n && ok; ++k) {
              if (k != i && arr[k].find(sub) != string::npos) {
                ok = false;
              }
            }
            if (ok) {
              ans[i] = sub;
            }
          }
        }
      }
    }
    return ans;
  }
};

func shortestSubstrings(arr []string) []string {
  ans := make([]string, len(arr))
  for i, s := range arr {
    m := len(s)
    for j := 1; j <= m && len(ans[i]) == 0; j++ {
      for l := 0; l <= m-j; l++ {
        sub := s[l : l+j]
        if len(ans[i]) == 0 || ans[i] > sub {
          ok := true
          for k, t := range arr {
            if k != i && strings.Contains(t, sub) {
              ok = false
              break
            }
          }
          if ok {
            ans[i] = sub
          }
        }
      }
    }
  }
  return ans
}

function shortestSubstrings(arr: string[]): string[] {
  const n: number = arr.length;
  const ans: string[] = Array(n).fill('');
  for (let i = 0; i < n; ++i) {
    const m: number = arr[i].length;
    for (let j = 1; j <= m && ans[i] === ''; ++j) {
      for (let l = 0; l <= m - j; ++l) {
        const sub: string = arr[i].slice(l, l + j);
        if (ans[i] === '' || sub.localeCompare(ans[i]) < 0) {
          let ok: boolean = true;
          for (let k = 0; k < n && ok; ++k) {
            if (k !== i && arr[k].includes(sub)) {
              ok = false;
            }
          }
          if (ok) {
            ans[i] = sub;
          }
        }
      }
    }
  }
  return ans;
}