LeetCode-in-All
438. Find All Anagrams in a String
Medium
Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.
An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
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".
Constraints:
1 <= s.length, p.length <= 3 * 104sandpconsist of lowercase English letters.
Solution
class Solution {
/**
* @param String $s
* @param String $p
* @return Integer[]
*/
public function findAnagrams($s, $p) {
$map = array_fill(0, 26, 0);
for ($i = 0; $i < strlen($p); ++$i) {
$map[ord($p[$i]) - ord('a')]++;
}
$res = array();
$i = 0;
$j = 0;
while ($i < strlen($s)) {
$idx = ord($s[$i]) - ord('a');
// add the new character
$map[$idx]--;
// if the length is greater than windows length, pop the left charcater in the window
if ($i >= strlen($p)) {
$map[ord($s[$j++]) - ord('a')]++;
}
$finish = true;
for ($k = 0; $k < 26; $k++) {
// if it is not an anagram of string p
if ($map[$k] != 0) {
$finish = false;
break;
}
}
if ($i >= strlen($p) - 1 && $finish) {
array_push($res, $j);
}
$i++;
}
return $res;
}
}