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

LeetCode438. 找到字符串中所有字母异位词

解题思路

由于题目要求在s串中找p串的异位词，因此我们不关心p串中的字符顺序，只关心其中各字母出现的频次。p串只有小写字母组成，对此可以定义一个大小为26的桶用来存储p中各字母的出现频次。在检查s串字串是否是异位词时，只需检查字串的各字母频次是否与p串完全相同。

至此可以写出暴力解法。遍历s串所有p.size()长度的子串，比较字母频次，相同时记录首字母坐标。

对暴力解法优化，可以发现统计子串频次时，只要发现子串某一字母(设为x)的计数大于s串中对应字母频次时，即可以判断该子串一定不是s的异位词；进一步，当前情况下，我们可以向右移动子串左端点，直到左右端点间x的计数刚好回到正常范围内，也就x的计数正好等于p中x的频次，再移动右端点，继续探索以当前左端点为起点的子串。这样就跳过了许多不可能成为p串异位词的子串起点。

实现代码

可以使用双指针或滑动窗口的思想实现代码

LeetCode代码：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        // 初始化一个大小为26的数组，用于记录字符串p中各个字母的出现次数
        int pbuck[26] = {0};
        int n = p.size();  // 字符串p的长度
        int m = s.size();  // 字符串s的长度

        // 遍历字符串p，统计各个字母的出现次数
        for (int i = 0; i < n; i++) {
            pbuck[p[i] - 'a']++;
        }

        // 用于记录滑动窗口中各个字母的出现次数
        int temp[26] = {0};
        int l = 0;  // 滑动窗口的左边界
        int r = 0;  // 滑动窗口的右边界
        vector<int> ans;  // 用于存储结果的向量

        // 开始滑动窗口
        while (l <= m - n && r < m) {
            // 向右扩展窗口，同时更新temp数组
            while (r - l + 1 <= n && r < m && ++temp[s[r] - 'a'] <= pbuck[s[r] - 'a']) {
                // 当窗口大小等于p的长度时，说明找到了一个anagram，记录左边界位置
                if (r - l + 1 == n) {
                    ans.push_back(l);
                    temp[s[l] - 'a']--;

                    // 移动左边界
                    if (l < m - n)
                        l++;
                    else
                        break;
                }
                r++;
            }

            // 若右边界达到字符串末尾，则退出循环
            if (r == m - 1) break;

            // 缩小窗口，更新temp数组
            while (l <= m - n && r < m && temp[s[r] - 'a'] > pbuck[s[r] - 'a']) {
                temp[s[l] - 'a']--;

                // 当前字母的出现次数与p中相等，移动右边界
                if (temp[s[r] - 'a'] == pbuck[s[r] - 'a']) r++;
                // 移动左边界
                l++;
            }
        }
        return ans;
    }
};

完整代码：

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

int main() {
    // 输出&quot;Hello, World!&quot;
    cout &lt;&lt; &quot;Hello, World!&quot; &lt;&lt; endl;

    // 输入两个字符串s和p
    string s;
    string p;
    cin &gt;&gt; s;
    cin &gt;&gt; p;

    // 初始化数组用于记录p中各个字母的出现次数
    int pbuck[26] = {0};
    int n = p.size();  // 字符串p的长度
    int m = s.size();  // 字符串s的长度

    // 遍历字符串p，统计各个字母的出现次数
    for (int i = 0; i &lt; n; i++) {
        pbuck[p[i] - &#039;a&#039;]++;
    }

    // 用于记录滑动窗口中各个字母的出现次数
    int temp[26] = {0};
    int l = 0;  // 滑动窗口的左边界
    int r = 0;  // 滑动窗口的右边界
    vector&lt;int&gt; ans;  // 用于存储结果的向量

    // 开始滑动窗口
    while (l &lt;= m - n &amp;&amp; r &lt; m) {
        // 向右扩展窗口，同时更新temp数组
        while (r - l + 1 &lt;= n &amp;&amp; r &lt; m &amp;&amp; ++temp[s[r] - &#039;a&#039;] &lt;= pbuck[s[r] - &#039;a&#039;]) {
            // 当窗口大小等于p的长度时，说明找到了一个anagram，记录左边界位置
            if (r - l + 1 == n) {
                ans.push_back(l);
                temp[s[l] - &#039;a&#039;]--;
                l++;
            }
            r++;
        }

        // 若右边界达到字符串末尾，则退出循环
        if (r &gt;= m - 1) break;

        // 缩小窗口，更新temp数组
        while (l &lt;= m - n &amp;&amp; r &lt; m &amp;&amp; temp[s[r] - &#039;a&#039;] &gt; pbuck[s[r] - &#039;a&#039;]) {
            temp[s[l] - &#039;a&#039;]--;

            // 当前字母的出现次数与p中相等，移动右边界
            if (l == r || temp[s[r] - &#039;a&#039;] == pbuck[s[r] - &#039;a&#039;]) r++;
            // 移动左边界
            l++;
        }
    }

    // 输出结果
    for (int i = 0; i &lt; ans.size(); i++) {
        cout &lt;&lt; ans[i] &lt;&lt; &#039; &#039;;
    }

    return 0;
}

运行结果

相关链接

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

我的LeetCode题解

LeetCode官方题解