LeetCode | Anagrams

发表于   |   分类于   |     |   阅读次数

§Anagrams

§Problem

  • 242. Valid Anagram

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    bool 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;
        }

  • 49. Group Anagrams

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// use sort & hashmap
vector<vector<string>> groupAnagrams(vector<string>& strs) {
  unordered_map<string,multiset<string>> ansmap;
  for (auto s:strs){
    string tmp = s;
    sort(tmp.begin(),tmp.end());
    ansmap[tmp].insert(s);
  }
  vector<vector<string>> ans;
  for (auto str:ansmap){
    vector<string> anstmp(str.second.begin(),str.second.end());
    ans.push_back(anstmp);
  }
  return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// use primer to present number
public List<List<String>> groupAnagrams(String[] strs) {
  int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
  List<List<String>> res = new ArrayList<>();
  HashMap<Integer, Integer> map= new HashMap<>();
  for (String s : strs){
    int key = 1;
    for (char c : s.toCharArray())
      key *= prime[c-'a'];
    //use index as value
    List<String> tmp;
    if (map.containsKey(key))
      tmp = res.get(map.get(key));
    else{
      tmp = new ArrayList<>();
      map.put(key, res.size());
      res.add(tmp);
    }
    tmp.add(s);
  }
  return res;
}

  • 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
    20
    public 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;
    }

  • 567. Permutation in String

    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
    17
    public 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