变位词组 | 徐年の博客

力扣面试题 10.02. 变位词组

题目说明

编写一种方法，对字符串数组进行排序，将所有变位词组合在一起。变位词是指字母相同，但排列不同的字符串。

注意：本题相对原题稍作修改
说明：
- 所有输入均为小写字母。
- 不考虑答案输出的顺序。

示例

示例1:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

笔者理解

此题是一道哈希表算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题采用哈希表进行记录比较容易求解，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * 哈希表
     * 排序
     */
    public List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> map = new HashMap<>();

        for (int i = 0; i < strs.length; i++) {
            // 将字符串转化为字节数组进行排序
            char[] ch = strs[i].toCharArray();
            Arrays.sort(ch);
            String s = new String(ch);
            List<String> temp;
            // 排序之后对当前字符串进行HashMap记录
            if (map.getOrDefault(s, null) == null) {
                temp = new ArrayList<>();
            }
            else {
                temp = map.get(s);
            }
            temp.add(strs[i]);
            map.put(s, temp);
        }

        List<List<String>> result = new ArrayList<>();
        // 取出所有变位词的记录
        for(List<String> list : map.values()) {
            result.add(list);
        }

        return result;
    }
}