哈希映射 + 滑动窗口，求解《438. 找到字符串中所有字母异位词》和《30. 串联所有单词的子串》
例题
438. 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
答案
哈希映射 · 滑动窗口
var findAnagrams = function(s, p) {
const sn = s.length, pn = p.length, h = new Int16Array(26), r = []
for (let i = 0; i < pn; i++) {
if (i < sn) h[s.charCodeAt(i) - 97]++
h[p.charCodeAt(i) - 97]--
}
let d = 0
for (let i = 0; i < 26; i++) if (h[i] != 0) d++
if (d === 0) r.push(0)
for (let i = 0; i + pn < sn; i++) {
if (h[s.charCodeAt(i) - 97] === 1) d--
if (h[s.charCodeAt(i) - 97] === 0) d++
h[s.charCodeAt(i) - 97]--
if (h[s.charCodeAt(i + pn) - 97] === -1) d--
if (h[s.charCodeAt(i + pn) - 97] === 0) d++
h[s.charCodeAt(i + pn) - 97]++
if (d === 0) r.push(i + 1)
}
return r
};function findAnagrams(s: string, p: string): number[] {
const h = new Int16Array(26), pn = p.length, sn = s.length, r = []
for (let i = 0; i < pn; i++) {
h[s.charCodeAt(i) - 97]++
h[p.charCodeAt(i) - 97]--
}
let d = 0
for (let i = 0; i < 26; i++) if (h[i] !== 0) d++
if (d === 0) r.push(0)
for (let i = 0; i < sn; i++) {
if (h[s.charCodeAt(i) - 97] === 1) d--
if (h[s.charCodeAt(i) - 97] === 0) d++
h[s.charCodeAt(i) - 97]--
if (h[s.charCodeAt(i + pn) - 97] === -1) d--
if (h[s.charCodeAt(i + pn) - 97] === 0) d++
h[s.charCodeAt(i + pn) - 97]++
if (d === 0) r.push(i + 1)
}
return r
};class Solution {
public List<Integer> findAnagrams(String s, String p) {
int[] h = new int[26];
List<Integer> r = new ArrayList<Integer>();
int pn = p.length(), sn = s.length();
for (int i = 0; i < pn; i++) {
if (i < sn) h[s.charAt(i) - 'a']++;
h[p.charAt(i) - 'a']--;
}
int d = 0;
for (int i = 0; i < 26; i++) if (h[i] != 0) d++;
if (d == 0) r.add(0);
for (int i = 0; i + pn < sn; i++) {
if (h[s.charAt(i) - 'a'] == 1) d--;
if (h[s.charAt(i) - 'a'] == 0) d++;
h[s.charAt(i) - 'a']--;
if (h[s.charAt(i + pn) - 'a'] == -1) d--;
if (h[s.charAt(i + pn) - 'a'] == 0) d++;
h[s.charAt(i + pn) - 'a']++;
if (d == 0) r.add(i + 1);
}
return r;
}
}func findAnagrams(s string, p string) []int {
sn, pn, h, d, r := len(s), len(p), make([]int, 26), 0, []int{}
for i := 0; i < pn; i++ {
if i < sn {
h[s[i] - 97]++
}
h[p[i] - 97]--
}
for i := 0; i < 26; i++ {
if h[i] != 0 {
d++
}
}
if d == 0 {
r = append(r, 0)
}
for i := 0; i + pn < sn; i++ {
if h[s[i] - 97] == 1 {
d--
}
if h[s[i] - 97] == 0 {
d++
}
h[s[i] - 97]--
if h[s[i + pn] - 97] == -1 {
d--
}
if h[s[i + pn] - 97] == 0 {
d++
}
h[s[i + pn] - 97]++
if d == 0 {
r = append(r, i + 1)
}
}
return r
}class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
sn, pn, h, r, d = len(s), len(p), [0] * 26, [], 0
for i in range(0, pn):
if i < sn: h[ord(s[i]) - 97] += 1
h[ord(p[i]) - 97] -= 1
for i in range(0, 26):
if h[i] != 0: d += 1
if d == 0: r.append(0)
for i in range(0, sn - pn):
if h[ord(s[i]) - 97] == 1: d -= 1
if h[ord(s[i]) - 97] == 0: d += 1
h[ord(s[i]) - 97] -= 1
if h[ord(s[i + pn]) - 97] == -1: d -= 1
if h[ord(s[i + pn]) - 97] == 0: d += 1
h[ord(s[i + pn]) - 97] += 1
if d == 0: r.append(i + 1)
return rclass Solution {
function findAnagrams($s, $p) {
$sn = strlen($s);
$pn = strlen($p);
$h = array_fill(0, 26, 0);
$r = [];
for ($i = 0; $i < $pn; $i++) {
if ($i < $sn) $h[ord($s[$i]) - 97]++;
$h[ord($p[$i]) - 97]--;
}
$d = 0;
for ($i = 0; $i < 26; $i++) if ($h[$i] != 0) $d++;
if ($d === 0) $r []= 0;
for ($i = 0; $i + $pn < $sn; $i++) {
if ($h[ord($s[$i]) - 97] === 1) $d--;
if ($h[ord($s[$i]) - 97] === 0) $d++;
$h[ord($s[$i]) - 97]--;
if ($h[ord($s[$i + $pn]) - 97] === -1) $d--;
if ($h[ord($s[$i + $pn]) - 97] === 0) $d++;
$h[ord($s[$i + $pn]) - 97]++;
if ($d === 0) $r []= $i + 1;
}
return $r;
}
}int* findAnagrams(char * s, char * p, int* returnSize){
int sn = strlen(s), pn = strlen(p);
int *r = (int *)malloc(sizeof(int) * sn);
int h[26] = {0};
for (int i = 0; i < pn; i++) {
if (i < sn) h[s[i] - 97]++;
h[p[i] - 97]--;
}
int d = 0, j = 0;
for (int i = 0; i < 26; i++) {
if (h[i] != 0) d++;
}
if (d == 0) r[j++] = 0;
for (int i = 0; i + pn < sn; i++) {
if (h[s[i] - 97] == 1) d--;
if (h[s[i] - 97] == 0) d++;
h[s[i] - 97]--;
if (h[s[i + pn] - 97] == -1) d--;
if (h[s[i + pn] - 97] == 0) d++;
h[s[i + pn] - 97]++;
if (d == 0) r[j++] = i + 1;
}
*returnSize = j;
return r;
}class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> r;
vector<int> h(26);
int sn = s.length(), pn = p.length();
for (int i = 0; i < pn; i++) {
if (i < sn) h[s[i] - 'a']++;
h[p[i] - 'a']--;
}
int d = 0;
for (int i = 0; i < 26; i++) if (h[i] != 0) d++;
if (d == 0) r.emplace_back(0);
for (int i = 0; i + pn < sn; i++) {
if (h[s[i] - 'a'] == 1) d--;
if (h[s[i] - 'a'] == 0) d++;
h[s[i] - 'a']--;
if (h[s[i + pn] - 'a'] == -1) d--;
if (h[s[i + pn] - 'a'] == 0) d++;
h[s[i + pn] - 'a']++;
if (d == 0) r.emplace_back(i + 1);
}
return r;
}
};public class Solution {
public IList<int> FindAnagrams(string s, string p) {
int sn = s.Length, pn = p.Length;
IList<int> r = new List<int>();
int[] h = new int[26];
for (int i = 0; i < pn; i++) {
if (i < sn) h[s[i] - 'a']++;
h[p[i] - 'a']--;
}
int d = 0;
for (int i = 0; i < 26; i++) if (h[i] != 0) d++;
if (d == 0) r.Add(0);
for (int i = 0; i + pn < sn; i++) {
if (h[s[i] - 'a'] == 1) d--;
if (h[s[i] - 'a'] == 0) d++;
h[s[i] - 'a']--;
if (h[s[i + pn] - 'a'] == -1) d--;
if (h[s[i + pn] - 'a'] == 0) d++;
h[s[i + pn] - 'a']++;
if (d == 0) r.Add(i + 1);
}
return r;
}
}30. 串联所有单词的子串
给定一个字符串 s 和一些 长度相同 的单词 words 。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符 ，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
答案
哈希映射 · 滑动窗口
var findSubstring = function(s, words) {
const sn = s.length, wn = words.length, n = words[0].length, r = []
for (let i = 0; i + wn * n <= sn && i < n; i++) {
const d = new Map()
for (let j = 0; j < wn; j++) {
add(d, s.slice(i + j * n, i + (j + 1) * n), 1)
add(d, words[j], -1)
}
for (let j = i; j + wn * n <= sn; j += n) {
if (j !== i) {
add(d, s.slice(j + (wn - 1) * n, j + wn * n), 1)
add(d, s.slice(j - n, j), -1)
}
if (d.size === 0) r.push(j)
}
}
return r
};
const add = (d, w, n) => {
d.set(w, (d.get(w) || 0) + n)
if (d.get(w) === 0) d.delete(w)
}function findSubstring(s: string, words: string[]): number[] {
const sn = s.length, wn = words.length, n = words[0].length, r = [], add = (d, w, n) => {
d[w] = (d[w] || 0) + n
if (d[w] === 0) delete d[w]
}
for (let i = 0; i + wn * n <= sn && i < n; i++) {
const d = Object.create(null)
for (let j = 0; j < wn; j++) {
add(d, s.slice(i + j * n, i + (j + 1) * n), 1)
add(d, words[j], -1)
}
if (Object.keys(d).length === 0) r.push(i)
for (let j = i + n; j + wn * n <= sn; j += n) {
add(d, s.slice(j + (wn - 1) * n, j + wn * n), 1)
add(d, s.slice(j - n, j), -1)
if (Object.keys(d).length === 0) r.push(j)
}
}
return r
};class Solution {
private Map<String, Integer> d = new HashMap<String, Integer>();
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> r = new ArrayList<Integer>();
int sn = s.length(), wn = words.length, n = words[0].length();
for (int i = 0; i + wn * n <= sn && i < n; i++) {
for (int j = 0; j < wn; j++) {
add(s.substring(i + j * n, i + (j + 1) * n), 1);
add(words[j], -1);
}
if (d.size() == 0) r.add(i);
for (int j = i + n; j + wn * n <= sn; j += n) {
add(s.substring(j + (wn - 1) * n, j + wn * n), 1);
add(s.substring(j - n, j), -1);
if (d.size() == 0) r.add(j);
}
d.clear();
}
return r;
}
public void add(String w, int n) {
d.put(w, d.getOrDefault(w, 0) + n);
if (d.get(w) == 0) d.remove(w);
}
}func findSubstring(s string, words []string) []int {
sn, wn, n, r, d := len(s), len(words), len(words[0]), []int{}, map[string]int{}
var add func(w string, n int)
add = func(w string, n int) {
if _, ok := d[w]; ok == false {
d[w] = 0
}
d[w] += n
if d[w] == 0 {
delete(d, w)
}
}
for i := 0; i + wn * n <= sn && i < n; i++ {
d = map[string]int{}
for j := 0; j < wn; j++ {
add(s[i + j * n : i + (j + 1) * n], 1)
add(words[j], -1)
}
if len(d) == 0 {
r = append(r, i)
}
for j := i + n; j + wn * n <= sn; j += n {
add(s[j + (wn - 1) * n : j + wn * n], 1)
add(s[j - n : j], -1)
if len(d) == 0 {
r = append(r, j)
}
}
}
return r
}class Solution {
function findSubstring($s, $words) {
$sn = strlen($s);
$wn = count($words);
$n = strlen($words[0]);
$r = [];
for ($i = 0; $i + $wn * $n <= $sn && $i < $n; $i++) {
$d = array();
for ($j = 0; $j < $wn; $j++) {
$this->add($d, substr($s, $i + $j * $n, $n), 1);
$this->add($d, $words[$j], -1);
}
if (count($d) === 0) $r []= $i;
for ($j = $i + $n; $j + $wn * $n <= $sn; $j += $n) {
$this->add($d, substr($s, $j + ($wn - 1) * $n, $n), 1);
$this->add($d, substr($s, $j - $n, $n), -1);
if (count($d) === 0) $r []= $j;
}
}
return $r;
}
function add(&$d, $w, $n) {
$d[$w] = $d[$w] + $n;
if ($d[$w] === 0) unset($d[$w]);
}
}class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
sn, wn, n, r, d = len(s), len(words), len(words[0]), [], {}
def add(w, n):
d.setdefault(w, 0)
d[w] += n
if d[w] == 0: d.pop(w)
for i in range(0, min(n, sn - wn * n + 1)):
d.clear()
for j in range(0, wn):
add(s[i + j * n : i + (j + 1) * n], 1)
add(words[j], -1)
if len(d) == 0: r.append(i)
for j in range(i + n, sn - wn * n + 1, n):
add(s[j + (wn - 1) * n : j + wn * n], 1)
add(s[j - n: j], -1)
if len(d) == 0: r.append(j)
return r class Solution {
public:
unordered_map <string, int> d;
vector<int> findSubstring(string s, vector<string>& words) {
int sn = s.size(), wn = words.size(), n = words[0].size();
vector<int> r;
for (int i = 0; i + wn <= sn && i < n; i++) {
d.clear();
for (int j = 0; j < wn; j++) {
add(s.substr(i + j * n, n), 1);
add(words[j], -1);
}
if (d.size() == 0) r.push_back(i);
for (int j = i + n; j + wn * n <= sn; j += n) {
add(s.substr(j + (wn - 1) * n, n), 1);
add(s.substr(j - n, n), -1);
if (d.size() == 0) r.push_back(j);
}
}
return r;
}
void add(string w, int n) {
d[w] += n;
if (d[w] == 0) d.erase(w);
}
};public class Solution {
private Dictionary<string, int> d = new Dictionary<string, int>();
public IList<int> FindSubstring(string s, string[] words) {
int sn = s.Length, wn = words.Length, n = words[0].Length;
IList<int> r = new List<int>();
for (int i = 0; i + wn * n <= sn && i < n; i++) {
for (int j = 0; j < wn; j++) {
add(s.Substring(i + j * n, n), 1);
add(words[j], -1);
}
if (d.Count == 0) r.Add(i);
for (int j = i + n; j + wn * n <= sn; j += n) {
add(s.Substring(j + (wn - 1) * n, n), 1);
add(s.Substring(j - n, n), -1);
if (d.Count == 0) r.Add(j);
}
d.Clear();
}
return r;
}
public void add(string w, int n) {
if (d.ContainsKey(w) == false) d.Add(w, 0);
d[w] += n;
if (d[w] == 0) d.Remove(w);
}
}