Anagrams

描述

Given an array of strings, return all groups of strings that are anagrams.

Note: All inputs will be in lower-case.

分析

Anagram（回文构词法）是指打乱字母顺序从而得到新的单词，比如 "dormitory" 打乱字母顺序会变成 "dirty room" ，"tea" 会变成"eat"。

回文构词法有一个特点：单词里的字母的种类和数目没有改变，只是改变了字母的排列顺序。因此，将几个单词按照字母顺序排序后，若它们相等，则它们属于同一组 anagrams 。

代码

  1. // Anagrams
  2. // 时间复杂度O(n)，空间复杂度O(n)
  3. public class Solution {
  4.     public List<List<String>> groupAnagrams(String[] strs) {
  5.         final HashMap<String, ArrayList<String>> group = new HashMap<>();
  6.         for (final String s : strs) {
  7.             char[] tmp = s.toCharArray();
  8.             Arrays.sort(tmp);
  10.             final String key = new String(tmp);
  11.             if (!group.containsKey(key)) {
  12.                 group.put(key, new ArrayList<>());
  13.             }
  14.             group.get(key).add(s);
  15.         }
  17.         List<List<String>> result = new ArrayList<>();
  18.         for (Map.Entry<String, ArrayList<String>> entry : group.entrySet()) {
  19.             final ArrayList<String> list = entry.getValue();
  20.             Collections.sort(list);
  21.             result.add(list);
  22.         }
  23.         return result;
  24.     }
  25. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/string/anagrams.html