找到字符串中所有字符异位词
题目
给定一个字符串s和一个非空字符串p，找到s中所有是p的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串s和 p的长度都不超过 20100。
说明：
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例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" 的字母异位词。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
异位词的起始索引,在于怎么判断当前长度一样的字符串是p的异位词
比较简单的一个想法就是二次遍历,从p的长度开始向前比较.但是会超过时间限制
比较复杂的是Mr_Tao在领扣上发布的
准备工作：
-
设置两个指针 起始坐标start=0，一个结束坐标end=0
-
建立两个长度为26的int数组，p_letter记录p里面的字母分别都有多少个，between_letter记录两个指针中的字母分别都有多少个
正式开始： -
做一个循环，start先不动，拿到end指针对应的字母，between_letter中字母对应的数量加1，并让end自增
-
判断一下，这个字母的数字是不是比p_letter要多了，如果是，表示出现了下面两种情况中的一种
1.start到end中的字母数量比p的length大,那么肯定至少会有一个字母的数量比p_letter里多
2.start到end的距离小于等于p的length，但是里面的某一个字母比p多
不管是上述情况中哪一种，start都应该前进，直到这个字母的数量等于p中的字母数量。（做完这一步start和end之间的字母数量一定小于等于p的length） -
然后再判断一下，start和end之间的字母数量是不是等于p的length。如果是，表示两个坐标之间的字母和p的字母构成一样
因为第二步中，一出现start和end之间的字母比p多，我们就让start前进，直到这个字母数量等于p里面的数量，确保了没有任何一个字母比p里面多
当start和end之间的字母数量和p里面的一样，且start和end之间没有任何一个字母比p多，就说明他们的字母组成一模一样
（因为数量一样的情况下，如果出现某个字母比p少，就一定会有另外一个字母比p多，这是充要条件）
作者：bugFactor
链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/solution/shuang-zhi-zhen-hua-kuai-by-mr_tao/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
利用双指针及数组的记录来保证.效率很高
代码
简单的,仅做参考,会超出时间限制
class Solution {
public List<Integer> findAnagrams(String s, String p) {
//异位词的起始索引,在于怎么判断当前长度一样的字符串是p的异位词.
//办法一,依次遍历s,判断p的副本中的字符
List<Integer> result = new ArrayList();
StringBuilder pCopy = new StringBuilder(p);
for (int i = p.length()-1; i < s.length(); i++) {
for (int j = i - p.length()+1; j < i+1; j++) {
if (pCopy.indexOf(s.charAt(j) + "") != -1) {
pCopy.deleteCharAt(pCopy.indexOf(s.charAt(j) + ""));
} else {
pCopy = new StringBuilder(p);
break;
}
if (pCopy.length() == 0) {
result.add(j - p.length()+1);
pCopy = new StringBuilder(p);
break;
}
}
}
return result;
}
}
使用双指针及数组
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList();
int start = 0;
int end = 0;
int[] p_pattern = new int[26];
int[] temp_pattern = new int[26];
for(int i = 0;i < p.length();i++){
p_pattern[p.charAt(i)-'a']++;
}
while(end < s.length()){
char c = s.charAt(end++); //取出当前字符
temp_pattern[c-'a']++; //在临时数组中添加位置
while (temp_pattern[c-'a'] > p_pattern[c-'a']){
temp_pattern[s.charAt(start++)-'a']--; //循环到将当前位置的数字等于p数组为止
}
if((end - start) == p.length()){ //此时如果窗口大小等于p的长度即可认为相等
result.add(start);
}
}
return result;
}
}
网友评论