Kimi LeetCode 3999. 字符串变换后的最少分组数 Golang实现

以下是 LeetCode 3999. 字符串变换后的最少分组数 的 Go 实现。

—

核心思路

两个字符串等价，当且仅当：
– 偶数下标子序列 互为循环同构
– 奇数下标子序列 互为循环同构

因此，对每个字符串：
1. 分离出偶数/奇数下标字符
2. 用 Booth 算法 分别求最小循环表示
3. 用 `"minEven#minOdd"` 作为唯一标识，放入 `map` 统计
4. 返回不同标识的数量

—

完整代码

```go
func minimumGroups(words []string) int {
    groups := make(map[string]struct{})

    for _, word := range words {
        n := len(word)
        even := make([]byte, 0, (n+1)/2)
        odd := make([]byte, 0, n/2)

        // 分离偶数/奇数下标字符
        for i := 0; i < n; i++ {
            if i&1 == 0 {
                even = append(even, word[i])
            } else {
                odd = append(odd, word[i])
            }
        }

        // 分别求最小循环表示，组合成唯一标识
        key := minRotation(string(even)) + "#" + minRotation(string(odd))
        groups[key] = struct{}{}
    }

    return len(groups)
}

/**
 * Booth 算法：求字符串 s 的最小循环表示
 * 时间复杂度 O(n)，空间复杂度 O(n)
 */
func minRotation(s string) string {
    n := len(s)
    if n <= 1 {
        return s
    }

    // 拼接自身，方便处理循环
    ss := s + s
    i, j, k := 0, 1, 0

    for i < n && j < n && k < n {
        a := ss[i+k]
        b := ss[j+k]

        if a == b {
            k++
        } else if a > b {
            // i 开头的表示字典序更大，跳过
            i = i + k + 1
            if i <= j {
                i = j + 1
            }
            k = 0
        } else {
            // j 开头的表示字典序更大，跳过
            j = j + k + 1
            if j <= i {
                j = i + 1
            }
            k = 0
        }
    }

    start := i
    if j < start {
        start = j
    }
    return ss[start : start+n]
}
```

—

关键点说明

要点    说明    
等价判定    偶数子序列循环同构 且 奇数子序列循环同构    
Booth 算法    O(n) 求最小循环表示，互为循环同构的字符串有唯一标识    
Set 模拟    Go 中用 `map[string]struct{}` 模拟集合，内存占用最小    
字符串拼接    用 `"#"` 分隔两个最小表示，避免歧义    

—

复杂度分析

– 时间：`O(总字符数)`，所有 `words[i]` 长度之和 ≤ 5×10⁵
– 空间：`O(总字符数)`，存储子序列及 map

如果还需要 C / JavaScript / Kotlin 版本，或者对 Booth 算法的推导过程有疑问，随时告诉我！