Leetcode.0438 | 找到字符串中所有字母异位词

题目

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

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

示例

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

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

解决方法

根据“异位词”的定义，同一个单词的各个异位词之间，各个元素出现的次数是相等的。比如，"ab"和"ba"两个异位词之间，字母a和b都只出现了一次。然后，就可以用一个长度为26的数组来记录每个英文字母出现的次数。

接着，使用“滑动窗口”，设置left和right两个变量，left表示窗口的开始位置，right表示窗口的结束位置，区间[left,end]用来记录当前窗口中的元素。

在起始位置，滑动窗口的left值为0，right值为-1，此时窗口没有元素。

向右移动right，直到窗口内元素个数等于字符串p的长度。判断窗口中的内容是否是字符串p的异位词。

判断结束后，将窗口整体右移，继续判断窗口的新内容是否是p的异位词。

代码实现

class Solution {
public:vector findAnagrams(string s, string p) {int left = 0;int right = -1;vector res;vector sourceData(26,0);for(int i = 0;i < p.size();i ++){sourceData[p[i]-'a'] ++;}int windowLen = p.size();if(windowLen > s.size()) return res;while(right != s.size()){while((right-left+1) < windowLen){right ++;}vector targetData(26,0);for(int i = left;i <= right;i ++){targetData[s[i]-'a'] ++;}if(sourceData == targetData) //c++中可以直接比较两个vector是否相等{res.push_back(left);}left ++;right ++;}return res;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！