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

问题描述

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

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

解题思路1

注意：该解题思路是错误的，正确的是解题思路2

这道题目首先想到的肯定是通过多层循环来遍历：

1. 提取子串：遍历s字符串，提取长度和p相同的子串
2. 字符匹配：创建p的副本，对于提取的子串中的每个字符，尝试在p的副本中找到并移除。如果某个字符在p的副本中不存在，说明该子串不是异位词。
3. 结果记录：如果所有字符都成功匹配并且p的副本被完全清空，将当前起始位置添加到结果中。

代码实现

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> results;
        int p_len = p.length();
        int s_len = s.length();

        if (s_len < p_len)
            return results;

        // 遍历s中的每个可能的起始位置
        for (int start = 0; start <= s_len - p_len; ++start) {
            string substr = s.substr(start, p_len); // 获取当前考虑的子串
            string temp_p = p; // 创建p的一个副本以供修改

            // 遍历当前子串中的每个字符
            bool matched = true;
            for (char c : substr) {
                size_t pos = temp_p.find(c); // 在p的副本中查找当前字符
                if (pos != string::npos) {
                    temp_p.erase(pos, 1); // 如果找到，从p的副本中移除该字符
                } else {
                    matched = false; // 如果未找到，标记不匹配并跳出循环
                    break;
                }
            }

            if (matched && temp_p.empty()) { // 检查是否所有p中的字符都被匹配
                results.push_back(start);
            }
        }

        return results;
    }
};

当提交答案时提示“超出时间限制”。

回头来看这里的问题：

这种方法的时间复杂度较高，因为它涉及到在每个可能的子串中对每个字符进行查找和删除操作，每次删除操作可能涉及到字符串的重构，其时间复杂度最坏情况下接近O(n * m^2)，其中n是字符串s的长度，m是字符串p的长度。这可能在输入字符串较长时导致性能问题。

解题思路2

通过对上面思路的反思，我认为这道题吗不能用多层循环嵌套处理，所以还是从题目本身出发。

我发现最核心的就是如何判断子串是否为异位词，上面通过循环遍历比较来判断的效率太低，就不能用循环遍历比较了。

核心思路：因为异位词不关心字符的顺序，只关心字符能不能被匹配上，那就是要判断字符在子串中出现的次数和出现在p的次数是否相同，如果相同就说明子串属于异位词。

解决这一问题的核心思路是利用滑动窗口技术和字符频率统计：

1. 字符频率统计：首先，我们需要一个方式来快速判断两个字符串是否为异位词。最直接的方法是使用一个固定大小为26的数组（假设输入字符串只包含小写字母）来统计每个字母在字符串中出现的频率。

2. 滑动窗口：这是一种常用于处理数组和字符串的技术。基本思想是维护一个窗口，这个窗口可以增大也可以缩小，随着窗口的滑动，我们可以在O(1)的时间内更新窗口内的信息。在这个问题中，我们将窗口的大小固定为字符串p的长度，并在s中从左到右滑动这个窗口。

代码实现

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        if (s.size() < p.size())
            return result;

        // 创建字符频率表
        vector<int> p_count(26, 0), s_count(26, 0);
        for (char c : p) {
            p_count[c - 'a']++;
        }

        int left = 0, right = 0, p_length = p.size();
        while (right < s.size()) {
            // 增加右侧字符频率
            s_count[s[right] - 'a']++;

            // 当窗口大小等于p的长度时，比较两个频率表
            if (right - left + 1 == p_length) {
                if (s_count == p_count) {
                    result.push_back(left);
                }
                // 移动窗口，减少左侧字符频率
                s_count[s[left] - 'a']--;
                left++;
            }

            right++;
        }

        return result;
    }
};