找到字符串中所有字母异位词（LeetCode 438）

恋喵大鲤鱼

发布于 2023-12-12 10:07:39

2730

发布于 2023-12-12 10:07:39

文章被收录于专栏：C/C++基础

文章目录

1.问题描述
2.难度等级
3.热门指数
4.解题思路
- 方法一：暴力法
- 方法二：滑动窗口
参考文献

1.问题描述

给定两个字符串 s 和 p，找到 s 中所有 p 的「异位词」的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1：

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2：

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示：

s 和 p 仅包含小写字母

2.难度等级

Medium。

3.热门指数

★★★★☆

出题公司：阿里、腾讯、字节。

4.解题思路

方法一：暴力法

容易想到的解法是遍历字符串的所有字符，判断每个字符为起点、长度为 len§ 的子串是否是异位词。

如何判断是否是异位词呢？

异位词指由相同字母重排列形成的字符串（包括相同的字符串）。

通过定义，我们可以知道如果构成字符串的字母相同，且每个字母出现的次数相同，则为异位词。

关于数据结构的选择，可以使用 map 存储字母及其出现的个数。

时间复杂度： 这种解法的空间复杂度很高 O(len(s)*len(p))。

空间复杂度： O(len(p))。

注意：这种解法可以通过测试用例，但会超时。

下面以 Golang 为给出实现。

func findAnagrams(s string, p string) []int {
    pmap := make(map[rune]int)
    for _, r := range p {
        pmap[r] += 1
    }
    var positions []int

    for i := 0; i <= len(s) - len(p); {
        smap := make(map[rune]int)
        var jump bool
        for j := i; j - i < len(p); j++ {
            if _, ok := pmap[rune(s[j])]; !ok {
                i = j+1
                jump = true
                break
            }
            smap[rune(s[j])] += 1
        }
        if !jump {
            if maps.Equal(pmap, smap) {
                positions = append(positions, i)
            }
            i++
        }
    }
    return positions
}

方法二：滑动窗口

因为字符串 p 的异位词的长度一定与字符串 p 的长度相同，所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p 的异位词。

在算法的实现中，我们可以使用数组来存储字符串 p 和滑动窗口中每种字母的数量。

当字符串 s 的长度小于字符串 p 的长度时，字符串 s 中一定不存在字符串 p 的异位词。但是因为字符串 s 中无法构造长度与字符串 p 的长度相同的窗口，所以这种情况需要单独处理。

复杂度分析： O(m+(n−m)×Σ)，其中 n 为字符串 s 的长度，m 为字符串 p 的长度，Σ 为所有可能的字符数。我们需要 O(m) 来统计字符串 p 中每种字母的数量；需要 O(m) 来初始化滑动窗口；需要判断 n−m+1 个滑动窗口中每种字母的数量是否与字符串 p 中每种字母的数量相同，每次判断需要 O(Σ)。因为 s 和 p 仅包含小写字母，所以 Σ=26。

空间复杂度： O(Σ)。用于存储字符串 p 和滑动窗口中每种字母的数量。

func findAnagrams(s string, p string) []int {
    if len(s) < len(p) {
        return nil
    }

    var sCount, pCount [26]int
	
	// 初始化字符串 p 中每种字母的数量。
	// 初始化滑动窗口中每种字母的数量。
    for i := 0; i < len(p); i++ {
        sCount[s[i]-'a']++
        pCount[p[i]-'a']++
    }

    var r []int
    for i := 0; i <= len(s) - len(p); i++ {
        if sCount == pCount {
            r = append(r, i)
        }
        // 向右移动滑动窗口，移动一个字母。
        sCount[s[i]-'a']--
        if i+len(p) < len(s) {
            sCount[s[i+len(p)]-'a']++
        }
    }
    return r
}