-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path15.cpp
More file actions
executable file
·68 lines (62 loc) · 1.76 KB
/
Copy path15.cpp
File metadata and controls
executable file
·68 lines (62 loc) · 1.76 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
/*
@filename 15.cpp
@author caonan
@date 2022-03-27 08:47:59
@reference 剑指offer专项
@url https://leetcode-cn.com/problems/VabMRr/
@brief 给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
变位词 指字母相同，但排列不同的字符串。
*/
#include <assert.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
class Solution
{
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> ret;
if (s.length() < p.length()) {
return ret;
}
int counts[26]{0};
for (int i = 0; i < p.length(); i++) {
counts[p[i] - 'a']++;
counts[s[i] - 'a']--;
}
auto isAllZero = [](int arr[]) -> bool {
for (int i = 0; i < 26; i++) {
if (arr[i] != 0) {
return false;
}
}
return true;
};
if (isAllZero(counts)) {
ret.push_back(0);
}
for (int i = p.length(); i < s.length(); i++) {
counts[s[i] - 'a']--;
counts[s[i - p.length()] - 'a']++;
if (isAllZero(counts)) {
ret.push_back(i - p.length() + 1);
}
}
return ret;
}
// isAllZero函数实际上每次都遍历26次，可以针对这里做差值优化
vector<int> findAnagrams(string s, string p) {}
};
int main()
{
Solution s;
vector<int> ret{0, 6};
assert(s.findAnagrams("cbaebabacd", "abc") == ret);
vector<int> ret1{0, 1, 2};
assert(s.findAnagrams("abab", "ab") == ret1);
return 0;
}