LeetCode算法题(Go语言实现)_11

题目

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
进阶：
如果有大量输入的 S，称作 S1, S2, … , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

一、代码实现

基础解法（双指针法）

func isSubsequence(s string, t string) bool {
    i, j := 0, 0
    for i < len(s) && j < len(t) {
        if s[i] == t[j] {
            i++
        }
        j++
    }
    return i == len(s)
}

进阶解法（预处理+二分搜索）

func isSubsequenceAdvanced(s string, t string) bool {
    // 预处理：记录每个字符在t中的位置
    index := make(map[byte][]int)
    for i := 0; i < len(t); i++ {
        c := t[i]
        index[c] = append(index[c], i)
    }

    // 匹配s的每个字符
    currentPos := 0
    for i := 0; i < len(s); i++ {
        c := s[i]
        positions, exists := index[c]
        if !exists {
            return false
        }
        // 二分查找第一个>=currentPos的位置
        pos := sort.SearchInts(positions, currentPos)
        if pos == len(positions) {
            return false
        }
        currentPos = positions[pos] + 1
    }
    return true
}

二、算法分析

1. 核心思路

• 双指针法：通过两个指针同步遍历 s 和 t，匹配字符后移动 s 指针，最终判断 s 是否遍历完成。
• 预处理优化：针对大量 s 输入的情况，预处理 t 的结构（记录每个字符的索引位置），使用二分查找快速定位匹配位置，减少重复遍历 t 的时间。

2. 关键步骤

1. 双指针法：

   • 初始化 i（指向 s）和 j（指向 t）为0。
   • 每次匹配成功时 i 和 j 同时右移，否则仅 j 右移。
   • 当 i 遍历完 s 时返回 true。

2. 预处理优化：

   • 构建哈希表，记录 t 中每个字符的所有出现位置。
   • 对每个 s 的字符，在其对应的位置列表中二分查找第一个不小于当前匹配位置的值。

3. 复杂度

三、图解

四、边界条件与扩展

1. 边界条件

• s为空：空字符串是任何字符串的子序列。
• t为空：若s非空则返回false。
• s比t长：直接返回false。

2. 扩展验证

• 大规模数据：预处理方法可在O(1)时间内完成单次查询（预处理时间O(n)）。
• 特殊字符：算法天然支持所有ASCII字符（需扩展哈希表范围）。

3. 算法对比

五、总结

• 核心逻辑：双指针法通过同步遍历快速判断子序列关系，时间复杂度为O(n)；预处理方法通过空间换时间优化高频查询场景。
• 优化点：
  1. 双指针法的贪心策略确保匹配位置的最左对齐，避免回溯。
  2. 预处理方法利用哈希表+二分查找将单次查询复杂度降为O(mlogk)。
• 应用场景：实时数据流中的子序列匹配（如日志分析）、高频查询系统设计（如API服务）。