leetcode438：找到字符串中所有字母异位词

题目链接

leetcode

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

C++ 代码

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

/*
    本题参考：567. 字符串的排列。

    滑动窗口：
        使用两个指针 left 和 right 来定义滑动窗口的左右边界。
        窗口大小改变。
            当窗口内的字符个数小于 p 的字符个数时，窗口扩展。
            当窗口内的字符个数等于 p 的字符个数时，窗口收缩。
        遍历完成后，返回结果数组 res

    时间复杂度：O(n)
        其中 n 是字符串 s 的长度。
        每个字符最多被访问两次。
    空间复杂度：O(1)
       need 和 window 的大小与字符集的大小相关，通常为 O(1)。
       假设字符集为小写字母，大小固定为 26。
*/
class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> need, window;
        for (const char& c : p) {
            need[c] ++;
        }

        vector<int> res;
        int valid = 0;
        int left = 0, right = 0;
        while (right < s.size()) {
            // c 是将移入窗口的字符
            char c = s[right];
            right ++;
            // 窗口内数据进行更新
            if (need.count(c)) {
                window[c] ++;
                if (window[c] == need[c]) {
                    valid ++;
                }
            }
            
            // 判断左侧窗口是否收缩
            while (right - left >= p.size()) {
                // 当窗口符合条件时，将起始索引加入返回结果
                if (valid == need.size()) {
                    res.push_back(left);
                } 
                // d 是将移出窗口的字符
                char d = s[left];
                left ++;
                // 窗口内数据进行更新
                if (need.count(d)) {
                    if (window[d] == need[d]) {
                        valid --;
                    }
                    window[d] --;
                }
            }
        }

        return res;
    }
};

int main() {
    Solution solution;
    vector<string> s_cases = { "cbaebabacd", "abab" };
    vector<string> p_cases = { "abc", "ab" };

    for (int i = 0; i < s_cases.size(); i++) {
        vector<int> res = solution.findAnagrams(s_cases[i], p_cases[i]);
        cout << "Input: s = " << s_cases[i] << ", p = " << p_cases[i] << endl;
        cout << "Output: [";
        for (int index : res) {
            cout << index << ",";
        }
        cout << "]" << endl;
    }

    return 0;
}

Golang 代码

package main

import "fmt"

/*
   基本思路：
       使用两个字符频率映射来比较模式字符串和滑动窗口中的字符频率。
       逐渐向右移动窗口，每次移动后判断窗口中的字符频率是否与模式字符串的字符频率相同。
       若两者相同，则找到一个字母异位词，将其起始索引添加到结果切片中。

   时间复杂度：O(n)
       其中 n 是字符串 s 的长度。
       遍历字符串一次。
   空间复杂度：O(1)
       need 和 window 的大小与字符集的大小相关，通常为 O(1)。
       假设字符集为小写字母，大小固定为 26。
*/
func findAnagrams(s string, p string) []int {
    need := make(map[byte]int)
    window := make(map[byte]int)
    // 计算模式字符串 p 的字符频率
    for i := 0; i < len(p); i ++ {
        need[p[i]] ++
    }

    // res := []int{}
    res := make([]int, 0)
    left, right := 0, 0
    valid := 0
    for right < len(s) {
        c := s[right]
        right ++
        // 窗口内数据进行更新
        if _, ok := need[c]; ok {
            window[c] ++
            if window[c] == need[c] {
                valid ++
            }
        }
        // 判断左侧窗口是否收缩
        for right - left >= len(p) {
            if valid == len(need) {
                res = append(res, left)
            }
            d := s[left]
            left ++
            // 窗口内数据进行更新
            if _, ok := need[d]; ok {
                if window[d] == need[d] {
                    valid --
                }
                window[d] --
            }
        }
    }

    return res
}

func main() {
    // 测试用例
    testCases := []struct {
        s        string
        p        string
        expected []int
    }{
        {"cbaebabacd", "abc", []int{0,6}},
        {"abab", "ab", []int{0,1,2}},
    }

    for i, tc := range testCases {
        result := findAnagrams(tc.s, tc.p)
        fmt.Printf("Test Case %d, Input: s = %q, p = %q\n", i+1, tc.s, tc.p)
        resultStr := fmt.Sprintf("%v", result)
        expectedStr := fmt.Sprintf("%v", tc.expected)

        if resultStr == expectedStr {
            fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
        } else {
            fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
        }
    }
}