438. Find All Anagrams in a String
438. Find All Anagrams in a String
Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.
Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.
The order of output does not matter.
Example 1:
Input:
s: "cbaebabacd" p: "abc"
Output:
[0, 6]
Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".Example 2:
Input:
s: "abab" p: "ab"
Output:
[0, 1, 2]
Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".My Solutions:
anagram 的定义是两个单词里出现的字母相同。
方法1：naive，把string里每一个char的len = p的substring都检查一遍
Time: O(n), n = length of s
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (s == null || p == null || s.length() == 0 || p.length() == 0) return res;
int len = p.length();
for (int i = 0; i <= s.length() - len; i++) {
if (isAna(s.substring(i, i + len), p)) {
res.add(i);
}
}
return res;
}
private boolean isAna(String s, String p) {
int[] hash = new int[26];
for (int i = 0; i < p.length(); i++) {
hash[p.charAt(i) - 'a']++;
hash[s.charAt(i) - 'a']--;
}
for (int c : hash) {
if (c != 0) return false;
}
return true;
}
}方法2：
先创建一个256大小的int array，把p里所有字符出现的频率记录下来。用counter记录p的长度
然后用两个指针，left代表sliding window的左边，即单词的开始index，right向右移动创造sliding window。只要right没有到搜索s的最末端，就不停向右移动。
在移动的过程中，right所在的字符如果在p里，就把counter 减1。
检测counter是否为0。如果为0，说明p里的所有字符都已经找到，把left此时的数字加入结果。
无论如何，right所在的字符在int array里的频率减1。然后移动right，right++。
如果此时left和right之间的距离等于p的长度，说明window已经是p的长度。我们需要把left左移，让window继续前进。
首先看此时int array里left所在的数字。如果此数字大于等于0，说明l所在的这个字母在p里出现过，因为没有出现过的字母会是负数。之前counter在这个情况下减去过1，所以此时count++把这个1加回来。
无论如何要把int array里的left所在的字符频率也+1。left再右移，left++。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (s == null || p == null || s.length() == 0 || p.length() ==0) return res;
// 记录p里letter出现的频率
int[] hash = new int[256];
for (char c : p.toCharArray()) hash[c]++;
//counter is a number to record whether we have a anagram which has equal length as p
int left = 0, right = 0, counter = p.length();
while (right < s.length()) {
// there is p's char in s，把counter减少1
char curr = s.charAt(right);
if (hash[curr] >= 1) counter--;
// 如果counter==0，说明每个在p里的字母都在s里找到了
if (counter == 0) res.add(left);
// hash table decreases the right char by 1
hash[curr]--;
right++; //move the sliding window to one step right
//if the window's size equals p, then we have to move left (narrow the window) to find the new match window
if (right - left == p.length()) {
// only increase the count if the character is in p，因为之前只有这样的条件才会count--
if (hash[s.charAt(left)] >= 0) counter++;
// 因为之前减少过hash[curr]--, 马上要移动left坐标，所以这里需要加1回来
hash[s.charAt(left)]++;
left++;
}
}
return res;
}
}Last updated