P115 变位词分组

描述#

这个题目说的是，给你一个字符串数组，你要把变位词划分到一组。其中，字符串只由小写字母组成。变位词指的是使用相同字母以不同顺序构成的单词。

比如说，给你的字符串数组是：
["eat", "tea", "ten", "ate", "net"]
将变位词分到一组，我们可以得到两个分组：
["eat", "tea", "ate"]
["ten", "net"]

代码#

public class AlgoCasts {

  private String getKeyBySort(String s) {
    char[] c = s.toCharArray();
    Arrays.sort(c);
    return new String(c);
  }

  // Time: O(k)
  private String getKeyByCount(String s) {
    char[] c = new char[26];
    for (int i = 0; i < s.length(); ++i)
      c[s.charAt(i) - 'a']++;
    return new String(c);
  }

  // Time: O(k)
  private String getKeyByCount2(String s) {
    int[] c = new int[26];
    for (int i = 0; i < s.length(); ++i)
      c[s.charAt(i) - 'a']++;
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < 26; ++i)
      if (c[i] != 0)
        sb.append((char)(i + 'a')).append(c[i]);
    return sb.toString();
  }

  // Time: O(n*k)
  // Time: O(n*k*log(k)), Space: O(n)
  public List<List<String>> groupAnagrams(String[] strs) {
    if (strs == null || strs.length == 0) return new ArrayList<>();
    Map<String, List<String>> map = new HashMap<>();

    for (String str: strs) {
      String key = getKeyBySort(str);
      map.putIfAbsent(key, new ArrayList<>());
      map.get(key).add(str);
    }
    return new ArrayList<>(map.values());
  }

}