§Anagrams
§Problem
-
1
2
3
4
5
6
7
8
9
10
11
12
13
14bool isAnagram(string s, string t) {
int l1=s.length();
if (l1!=t.length())
return false;
vector<int> cnt(256,0);
for (char ch:s)
cnt[ch]++;
for (char ch:t){
cnt[ch]--;
if (cnt[ch]<0)
return false;
}
return true;
}
1 | // use sort & hashmap |
1 | // use primer to present number |
-
438. Find All Anagrams in a String
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21// Sliding window
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
vector<int> ch1(26,0), ch2(26,0);
int l1 = s.length(), l2 = p.length();
if (l1<l2)
return ans;
for (int i=0; i<l2;i++){
ch1[s[i]-'a']++;
ch2[p[i]-'a']++;
}
if (ch1==ch2)
ans.push_back(0);
for (int i=l2;i<l1;i++){
ch1[s[i-l2]-'a']--;
ch1[s[i]-'a']++;
if (ch1==ch2)
ans.push_back(i-l2+1);
}
return ans;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
if (s == null || s.length() == 0 || p == null || p.length() == 0)
return res;
int[] les = new int[256];
for (char c : p.toCharArray())
++ les[c];
int l = 0, r = 0, cnt = p.length();
int len1 = p.length(), len2 = s.length();
while (r < len2){
// right letter s[r] exist in p that has been matched
if (les[s.charAt(r++)]-- >= 1)
-- cnt;
if (cnt == 0)
res.add(l);
// left letter s[l] exist in p that shoule be matched letter
if (r - l == len1 && les[s.charAt(l++)]++ >= 0) cnt++;
}
return res;
} -
the first string’s permutations is the substring of the second string -> find anagram
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20// Silimar to 567
bool checkInclusion(string p, string s) {
vector<int> ch1(26,0), ch2(26,0);
int l1 = s.length(), l2 = p.length();
if (l1<l2)
return false;
for (int i=0; i<l2;i++){
ch1[s[i]-'a']++;
ch2[p[i]-'a']++;
}
if (ch1==ch2)
return true;
for (int i=l2;i<l1;i++){
ch1[s[i-l2]-'a']--;
ch1[s[i]-'a']++;
if (ch1==ch2)
return true;
}
return false;
}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17public boolean checkInclusion(String s1, String s2) {
int [] les = new int[256];
for (char c : s1.toCharArray())
++ les[c];
int l = 0, r = 0, cnt = s1.length();
int len1 = s1.length(), len2 = s2.length();
while (r < len2){
// right letter s[r] exist in p that has been matched
if (les[s2.charAt(r++)]-- >= 1)
-- cnt;
if (cnt == 0)
return true;
// left letter s[l] exist in p that shoule be matched letter
if (r - l == len1 && les[s2.charAt(l++)]++ >= 0) cnt++;
}
return false;
}
§Conclusion
Normally it is related to HashMap, sort, two pointer