2025-08-06：最短公共超序列的字母出现频率。用go语言，给定一个字符串数组 words，要求找出所有的最短公共超序列。这些最短公共超序列的定义是：每个字符串都是该超序列的子序列，且超序列的长度最短。同时，这些最短公共超序列之间不能通过简单的字母排列互相转换。

输出需要是一个二维整数数组 freqs，表示所有找到的最短公共超序列。freqs 中的每个元素是一个长度为 26 的数组，统计该最短公共超序列中每个小写字母出现的次数。结果可以以任意顺序返回。

注：这里的“子序列”指的是从一个字符串中删除部分字符（可不删除）后，剩下字符保持原有顺序形成的新字符串（且非空）。

1 <= words.length <= 256。

words[i].length == 2。

words 中所有字符串由不超过 16 个互不相同的小写英文字母组成。

words 中的字符串互不相同。

输入：words = ["ab","ba"]。

输出：[[1,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],[2,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]]。

解释：

两个最短公共超序列分别是 "aba" 和 "bab" 。输出分别是两者的字母出现频率。

题目来自力扣3435。

解决步骤

  1. 收集字母和建图：

    • 遍历所有 words 中的字符串，记录所有出现的字母（all 掩码）。
    • 对于每个字符串的两个字母 x 和 y，在图中建立一条从 x 到 y 的边（有向图）。
    • 记录所有自环的字母（即 x == y 的情况，mask2 掩码）。

  2. 检查子集是否有环：

    • 对于 mask1（即 all ^ mask2，非自环字母的子集），枚举其所有子集 sub。
    • 对于每个子集 sub，检查图中由 sub 和 mask2 组成的子图是否有环（使用DFS或拓扑排序）。
    • 如果没有环，则记录该子集 sub 的大小（即子集中字母的数量），并保留最大大小的子集。

  3. 收集最大无环子集：

    • 维护一个集合 set，保存所有最大大小的无环子集 sub。
    • 如果发现更大的子集，清空 set 并更新最大大小。

  4. 生成字母频率：

    • 对于每个无环子集 sub，生成字母频率：
      • 自环字母（mask2）必须出现至少一次。
      • 非自环字母（sub 中的字母）出现一次，其余非自环字母（mask1 ^ sub）出现两次。
    • 将频率统计结果存入答案列表 ans。

示例分析

以 words = ["ab", "ba"] 为例：

  1. 字母集合：{'a', 'b'}，all = 0b11，mask2 = 0（无自环），mask1 = 0b11。
  2. 子集枚举：
    • sub = 0b11：检查是否有环（a->b 和 b->a 形成环），有环，跳过。
    • sub = 0b10（{'a'}）：无环（只有 a），记录。
    • sub = 0b01（{'b'}）：无环（只有 b），记录。
    • sub = 0b00：大小小于最大值，忽略。
  3. 最大无环子集：{'a'} 和 {'b'}。
  4. 生成频率：
    • {'a'}：a 出现1次，b 出现2次 → [1, 2, ...]。
    • {'b'}：a 出现2次，b 出现1次 → [2, 1, ...]。

时间复杂度和空间复杂度

  • 时间复杂度：
    • 枚举子集：O(3^k)，其中 k 是非自环字母的数量（mask1 的子集枚举）。
    • 检查环：每次 O(k + E)，其中 E 是边的数量（最多 O(n)，n 是 words 的数量）。
    • 总时间复杂度：O(3^k * (k + n))，其中 k <= 16。
  • 空间复杂度：
    • 存储图：O(26 + n)。
    • 存储子集和频率：O(2^k * 26)。
    • 总空间复杂度：O(2^k * 26 + n)。

总结

该算法通过枚举字母子集和检查环的存在性，高效地找到了所有最短公共超序列的字母频率。其核心在于利用位掩码和图的环检测来避免无效的子集。

Go完整代码如下：

package mainimport ("fmt""math/bits"
)func supersequences(words []string) [][]int {// 收集有哪些字母，同时建图all, mask2 := 0, 0g := [26][]int{}for _, s := range words {x, y := int(s[0]-'a'), int(s[1]-'a')all |= 1<<x | 1<<yif x == y {mask2 |= 1 << x}g[x] = append(g[x], y)}// 判断是否有环hasCycle := func(sub int) bool {color := [26]int8{}var dfs func(int) booldfs = func(x int) bool {color[x] = 1for _, y := range g[x] {// 只遍历在 sub 中的字母if sub>>y&1 == 0 {continue}if color[y] == 1 || color[y] == 0 && dfs(y) {return true}}color[x] = 2return false}for i, c := range color {// 只遍历在 sub 中的字母if c == 0 && sub>>i&1 > 0 && dfs(i) {return true}}return false}set := map[int]struct{}{}maxSize := 0mask1 := all ^ mask2// 枚举 mask1 的所有子集 subfor sub, ok := mask1, true; ok; ok = sub != mask1 {size := bits.OnesCount(uint(sub))// 剪枝：如果 size < maxSize 就不需要判断了if size >= maxSize && !hasCycle(sub) {if size > maxSize {maxSize = sizeclear(set)}set[sub] = struct{}{}}sub = (sub - 1) & mask1}ans := make([][]int, 0, len(set)) // 预分配空间for sub := range set {cnt := make([]int, 26)for i := range cnt {cnt[i] = all>>i&1 + (all^sub)>>i&1}ans = append(ans, cnt)}return ans
}func main() {words := []string{"ab", "ba"}result := supersequences(words)fmt.Println(result)
}

在这里插入图片描述

Python完整代码如下：

# -*-coding:utf-8-*-from typing import Listdef supersequences(words: List[str]) -> List[List[int]]:# 收集所有出现过的字母，以及构建有向图all_mask = 0mask2 = 0g = [[] for _ in range(26)]for s in words:x, y = ord(s[0]) - ord('a'), ord(s[1]) - ord('a')all_mask |= (1 << x) | (1 << y)if x == y:mask2 |= (1 << x)g[x].append(y)def hasCycle(sub: int) -> bool:color = [0] * 26  # 0=未访问, 1=访问中, 2=已访问def dfs(u: int) -> bool:color[u] = 1for v in g[u]:if (sub >> v) & 1 == 0:continueif color[v] == 1 or (color[v] == 0 and dfs(v)):return Truecolor[u] = 2return Falsefor i in range(26):if ((sub >> i) & 1) and color[i] == 0:if dfs(i):return Truereturn Falseset_subs = {}max_size = 0mask1 = all_mask ^ mask2# 枚举 mask1 的所有子集sub = mask1while True:size = bin(sub).count('1')if size >= max_size and not hasCycle(sub):if size > max_size:max_size = sizeset_subs.clear()set_subs[sub] = Noneif sub == 0:breaksub = (sub - 1) & mask1ans = []for sub in set_subs:cnt = [0] * 26for i in range(26):cnt[i] = ((all_mask >> i) & 1) + (((all_mask ^ sub) >> i) & 1)ans.append(cnt)return ansif __name__ == "__main__":words = ["ab", "ba"]result = supersequences(words)print(result)

在这里插入图片描述