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.length
• 2 <= n <= 100
• 1 <= arr[i].length <= 20
• arr[i] 只包含小写英文字母。

---

解题分析及思路：

思路：

本题可以采用哈希表的方式来解决：

• 首先我们需要遍历数组，将每个字符串的所有子字符串存入哈希表中，统计每个子字符串出现的次数，注意需要保证单个字符串的子字符串只存一次
• 然后再次遍历数组，在哈希表中找出每个字符串所对应的最短非公共子字符串，注意需要优先遍历长度最长的子字符串，因为这样保证了字典序最小。

最短非公共子字符串满足要求：

• 在哈希表中仅出现过一次，出现过一次即代表没有在其他字符串中出现过
• 长度最短，因为我们是优先遍历长度最长的子字符串，所以长度最短的子字符串一定是最短非公共子字符串

func shortestSubstrings(arr []string) []string {
	var subM = make(map[string]int)
	for index := range arr {
		var m = make(map[string]bool)
		for left := 0; left < len(arr[index]); left++ {
			for right := len(arr[index]); right >= left+1; right-- {
				m[arr[index][left:right]] = true
			}
		}
		for key := range m {
			subM[key]++
		}
	}
	var results []string
	for index := range arr {
		var result string = arr[index]
		var flag bool
		var left, count = 0, len(arr[index])
		for count > 0 {
			right := left + count
			for right <= len(arr[index]) {
				subS := arr[index][left:right]
				if v, ok := subM[subS]; ok && v == 1 && (len(subS) < len(result) || subS <= result) {
					result = subS
					flag = true
				}
				left++
				right++
			}
			count--
			left = 0
		}
		if !flag {
			result = ""
		}
		results = append(results, result)
	}
	return results
}

复杂度：

• 时间复杂度：O(M*N)
• 空间复杂度：O(M*N)

执行结果：

• 执行耗时:90 ms,击败了100.00% 的Go用户
• 内存消耗:8.39 MB,击败了100.00% 的Go用户