對於每個左右端窮舉即可，不過別做成O(N4logN)就好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int sherlockAndAnagrams(string s) {
int ct=0,len=s.size();
for(int i=0;i<len;i++){
for(int j=i;j<len;j++){
multiset<char> st,tt;
for(int k=i;k<=j;k++){
st.insert(s[k]);
tt.insert(s[k]);
}
for(int k=i+1;k<len-(j-i);k++){
tt.insert(s[k+(j-i)]);
auto it=tt.find(s[k-1]);
if(it!=tt.end()) tt.erase(it);
if(tt==st) ct++;
}
}
}
return ct;
}
|