2025-08-06：最短公共超序列的字母出现频率。用go语言，给定一个字符串数组 words，要求找出所有的最短公共超序列。这

福大大架构师每日一题

发布于 2025-08-06 08:33:14

8700

代码可运行

运行总次数：0

代码可运行

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 main

import (
    "fmt"
    "math/bits"
)

func supersequences(words []string) [][]int {
    // 收集有哪些字母，同时建图
    all, mask2 := 0, 0
    g := [26][]int{}
    for _, s := range words {
        x, y := int(s[0]-'a'), int(s[1]-'a')
        all |= 1<<x | 1<<y
        if x == y {
            mask2 |= 1 << x
        }
        g[x] = append(g[x], y)
    }

    // 判断是否有环
    hasCycle := func(sub int)bool {
        color := [26]int8{}
        var dfs func(int)bool
        dfs = func(x int)bool {
            color[x] = 1
            for _, y := range g[x] {
                // 只遍历在 sub 中的字母
                if sub>>y&1 == 0 {
                    continue
                }
                if color[y] == 1 || color[y] == 0 && dfs(y) {
                    returntrue
                }
            }
            color[x] = 2
            returnfalse
        }
        for i, c := range color {
            // 只遍历在 sub 中的字母
            if c == 0 && sub>>i&1 > 0 && dfs(i) {
                returntrue
            }
        }
        returnfalse
    }

    set := map[int]struct{}{}
    maxSize := 0
    mask1 := all ^ mask2
    // 枚举 mask1 的所有子集 sub
    for sub, ok := mask1, true; ok; ok = sub != mask1 {
        size := bits.OnesCount(uint(sub))
        // 剪枝：如果 size < maxSize 就不需要判断了
        if size >= maxSize && !hasCycle(sub) {
            if size > maxSize {
                maxSize = size
                clear(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 List

def supersequences(words: List[str]) -> List[List[int]]:
    # 收集所有出现过的字母，以及构建有向图
    all_mask = 0
    mask2 = 0
    g = [[] 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] = 1
            for v in g[u]:
                if (sub >> v) & 1 == 0:
                    continue
                if color[v] == 1 or (color[v] == 0 and dfs(v)):
                    return True
            color[u] = 2
            return False

        for i in range(26):
            if ((sub >> i) & 1) and color[i] == 0:
                if dfs(i):
                    return True
        return False

    set_subs = {}
    max_size = 0
    mask1 = all_mask ^ mask2

    # 枚举 mask1 的所有子集
    sub = mask1
    while True:
        size = bin(sub).count('1')
        if size >= max_size and not hasCycle(sub):
            if size > max_size:
                max_size = size
                set_subs.clear()
            set_subs[sub] = None

        if sub == 0:
            break
        sub = (sub - 1) & mask1

    ans = []
    for sub in set_subs:
        cnt = [0] * 26
        for i in range(26):
            cnt[i] = ((all_mask >> i) & 1) + (((all_mask ^ sub) >> i) & 1)
        ans.append(cnt)

    return ans

if __name__ == "__main__":
    words = ["ab", "ba"]
    result = supersequences(words)
    print(result)