1+ // 438. 找到字符串中所有字母异位词
2+
3+
4+ /*
5+ 滑动窗口 + 数组：
6+ 1、s的长度小于p时，不能凑成异位词
7+ 2、因为字符串中的字符全是小写字母，可以用长度为26的数组记录字母出现的次数
8+ 3、设n = len(s), m = len(p)。记录p字符串的字母频次 pCount，和s字符串前m个字母频次 sCount
9+ 4、若 pCount 和 sCount 相等，说明两者字母相同，则找到第一个异位词索引 0
10+ 5、以p字符串长度m为滑动窗口大小，继续判断s字符串的字符，向右滑动过程，滑动窗口头部增加一个字母，尾部去掉一个字母，增减次数对应记录到sCount
11+ 6、每次滑动后都判断 pCount 和 sCount 是否相等，若相等则新增异位词索引
12+
13+ s = "cbaadbac", p = "abca"
14+
15+ sCount = [2,1,1,...], pCount = [2,1,1,...]
16+ c b a a d b a c
17+ ↑_____↑
18+ ====================
19+ sCount = [2,1,0,1..], pCount = [2,1,1,...]
20+ c b a a d b a c
21+ ↑_____↑
22+ */
23+ class Solution {
24+ public List <Integer > findAnagrams (String s , String p ) {
25+ int n = s .length (), m = p .length ();
26+ List <Integer > res = new ArrayList <>();
27+ if (n < m ) {
28+ return res ;
29+ }
30+ int [] sCount = new int [26 ];
31+ int [] pCount = new int [26 ];
32+ for (int i = 0 ; i < m ; i ++) {
33+ sCount [s .charAt (i ) - 'a' ]++;
34+ pCount [p .charAt (i ) - 'a' ]++;
35+ }
36+ if (Arrays .equals (sCount , pCount )) {
37+ res .add (0 );
38+ }
39+ for (int i = m ; i < n ; i ++) {
40+ sCount [s .charAt (i - m ) - 'a' ]--;
41+ sCount [s .charAt (i ) - 'a' ]++;
42+ if (Arrays .equals (sCount , pCount )) {
43+ res .add (i - m + 1 );
44+ }
45+ }
46+ return res ;
47+ }
48+ }
49+
50+
51+ /*
52+ 滑动窗口 + 双指针
53+ 1、定义左右指针，从索引0开始
54+ 2、右指针向右滑动过程，记录 sCount 增加字母次数，当同一字母 sCount 次数大于 pCount，说明窗口内出现了多余的字母，需要移除，
55+ 于是左指针向右滑动，缩小窗口范围，并记录 sCount 减少字母次数，直到该字母次数合法
56+ 3、每次 右指针扩大窗口 和 左指针缩小窗口 操作结束后，窗口内的字母都是符合p要求的字母，判断一下窗口大小是否等于p的长度，是则说明窗口内字母凑齐，是异位词，记录起始索引
57+
58+ s = "cbaebabacd", p = "abc"
59+
60+ sCount = [1,1,1,0,...], pCount = [1,1,1,0,...]
61+ c b a d a b c d
62+ ↑ ↑
63+ left right
64+ ====================
65+ sCount = [1,1,1,1,...], pCount = [1,1,1,0,...]
66+ c b a d a b c d
67+ ↑ ↑
68+ left right
69+ ====================
70+ sCount = [0,0,0,0,...], pCount = [1,1,1,0,...]
71+ c b a d a b c d
72+ ↑ ↑
73+ right left
74+ ====================
75+ sCount = [1,1,1,0,...], pCount = [1,1,1,0,...]
76+ c b a d a b c d
77+ ↑ ↑
78+ left right
79+ */
80+ class Solution {
81+ public List <Integer > findAnagrams (String s , String p ) {
82+ int n = s .length (), m = p .length ();
83+ List <Integer > res = new ArrayList <>();
84+ if (n < m ) {
85+ return res ;
86+ }
87+ int [] sCount = new int [26 ];
88+ int [] pCount = new int [26 ];
89+ for (int i = 0 ; i < m ; i ++) {
90+ pCount [p .charAt (i ) - 'a' ]++;
91+ }
92+ int left = 0 , right = 0 ;
93+ while (right < n ) {
94+ int index = s .charAt (right ) - 'a' ;
95+ sCount [index ]++;
96+ while (sCount [index ] > pCount [index ]) {
97+ sCount [s .charAt (left ) - 'a' ]--;
98+ left ++;
99+ }
100+ if (right - left + 1 == m ) {
101+ res .add (left );
102+ }
103+ right ++;
104+ }
105+ return res ;
106+ }
107+ }
0 commit comments