49.Group-Anagrams

49. Group Anagrams

题目地址

https://www.lintcode.com/problem/anagrams

https://leetcode.com/problems/group-anagrams/

题目描述

Given an array of strings, group anagrams together.

Example:

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

Note:
All inputs will be in lowercase.
The order of your output does not matter.

代码

Approach 1: Categorize by Sorted String

Map => key: sort

Complexity Analysis

• Time Complexity: O(_N_K_log_K), where N is the length of strs, and K is the maximum length of a string in strs. The outer loop has complexity O(_N) as we iterate through each string. Then, we sort each string in O(_K_log_K) time.

• Space Complexity: O(_N_K), the total information content stored in ans.

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
    if (strs.length == 0) return new ArrayList();

    Map<String, List> ans = new HashMap<String, List>();
    for (String s : strs) {
      char[] chs = s.toCharArray();
      Arrays.sort(chs);
      String key = String.valueOf(chs);
      if (!ans.containsKey(key)) {
        ans.put(key, new ArrayList());
        ans.get(key).add(s);
      } 
    }
    return new ArrayList(ans.values());
  }

}

Approach #2 Categorie by Count

class Solution {
  public List<List<String>> groupAnagrams(String[] strs) {
    if (strs.length == 0) return new ArrayList();
    Map<String, List> ans = new HashMap<String, List>();
    int[] count = new int[26];
    for (String s : strs) {
      Arrays.fill(count, 0);
      for (char c : s.toCharArray()) {
        count[c - 'a']++;
      }
      StringBuilder sb = new StringBuilder("");
      for (int i = 0; i < 26; i++) {
        sb.append('#');
        sb.append(count[i]);
      }
      String key = sb.toString();
      if (!ans.containsKey(key)) {
        ans.put(key, new ArrayList());
        ans.get(key).add(s);
      }
    }

    return new ArrayList(ans.values());
  }
}

Approach #3

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
   List<List<String>> result = new ArrayList<List<String>>();
    if (strs == null) return result;

    Map<String, ArrayList<String>> multiMap = new HashMap<String, ArrayList<String>>();
    for (String str : strs) {
      char[] strChar = str.toCharArray();
      Arrays.sort(strChar);
      String strSorted = String.valueOf(strChar);
      if (multiMap.containsKey(strSorted)) {
        ArrayList<String> aList = multiMap.get(strSorted);
        aList.add(str);
        multiMap.put(strSorted, aList);
      } else {
        ArrayList<String> aList = new ArrayList<String>();
        aList.add(str);
        multiMap.put(strSorted, aList);
      }
    }

    // add List group to result
    Set<String> keySet = multiMap.keySet();
    for (String key : keySet) {
      ArrayList<String> aList = multiMap.get(key);
      Collections.sort(aList);
      result.add(aList);
    }

    return result;
  }
}