49. Group Anagrams.md

49. Group Anagrams

---

leetcode-cn Daily Challenge on December 14th, 2020.

---

Difficulty : Medium

Related Topics : HashTable、String

---

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Example 2:

Input: strs = [""]
Output: [[""]]

Example 3:

Input: strs = ["a"]
Output: [["a"]]

Constraints:

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] consists of lower-case English letters.

---

Solution

• mine
  • Java

    • Runtime: 900 ms, faster than 5.06%, Memory Usage: 41.7 MB, less than 94.93% of Java online submissions

      // O(N^2)time
      // O(N)space
      public List<List<String>> groupAnagrams(String[] strs) {
          List<List<String>> res = new ArrayList<>();
          int n = strs.length;
          List<int[]> list = new ArrayList<>(n);
          for(int i = 0; i < n; i++){
              String t = strs[i];
              int[] arr = new int[26];
              for(char c : t.toCharArray()){
                  arr[c - 'a']++;
              }
              list.add(arr);
          }
          boolean[] used = new boolean[n];
          for(int i = 0; i < n; i++){
              if(used[i]) continue;
              List<String> temp = new ArrayList<>();
              temp.add(strs[i]);
              check(list, strs, temp,used, i);
              res.add(temp);
          }
          return res;
      }
      
      void check(List<int[]> list, String[] strs, List<String> res, boolean[] used, int i){
          int[] arr = list.get(i);
          for(int j = i + 1; j < list.size(); j++){
              if(used[j]) continue;
              boolean same = true;
              for(int t = 0; t < arr.length; t++){
                  if(arr[t] != list.get(j)[t]){
                      same = false;
                      break;
                  }
              }
              if(same) {
                  res.add(strs[j]);
                  used[j] = true;
              }
          }
      }
      

    • Runtime: 6 ms, faster than 78.03%, Memory Usage: 41.5 MB, less than 97.77% of Java online submissions

      // O(N * logN)time
      // O(N)space
      public List<List<String>> groupAnagrams(String[] strs) {
          List<List<String>> res = new ArrayList<>();
          if (strs == null || strs.length == 0) {
              return res;
          }
          HashMap<String, List<String>> map = new HashMap<>();
          for (String str : strs) {
              char[] arr = str.toCharArray();
              Arrays.sort(arr);
              String key = String.valueOf(arr);
              List<String> value = map.getOrDefault(key, new ArrayList<>());
              value.add(str);
              map.put(key, value);
          }
          res.addAll(map.values());
          return res;
      }
      

---

• the most votes

• Runtime: 4 ms, faster than 99.71%, Memory Usage: 42 MB, less than 67.89% of Java online submissions

  // O(N)time
  // O(N)space
  int[] arr = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
  public List<List<String>> groupAnagrams(String[] strs) {
      Map<Long, List<String>> map = new HashMap<>();
      int size = 0;
      for(String str : strs){
          long hash = getHash(str);
          List<String> list = map.getOrDefault(hash, new ArrayList<>());
          list.add(str);
          map.put(hash, list);
      }
      return new ArrayList<>(map.values());
  }
  
  long getHash(String str){
      if(str == null || str.length() == 0) return 0L;
      long res = 1;
      for(char c : str.toCharArray()){
          res *= arr[c - 'a'];
      }
      return res;
  }
  

---