面试题 10.02. 变位词组

申松朋

发布于：2021年7月17日

面试题 10.02. 变位词组

题目描述

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

示例:

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

说明：

所有输入均为小写字母。
不考虑答案输出的顺序。

题解一

问题分解

如何识别字符串是同一个变位词？
同一个变位词如何快速加入到对应的数组中？

思路：

对于第一个问题：

对将变位词进行计数排序，返回排序好的字符串，将返回的字符串作为哈希表的key，


import java.util.ArrayList;
import java.util.HashMap;
import java.util;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList();
        HashMap<String ,List<String>> map = new HashMap();

        for ( String str: strs) {
            String key = count(str);
            List<String> list;
            if (!map.containsKey(key)) {
                list = new ArrayList<String>();
                result.add(list);
                map.put(key,list);

            }else {
                list = map.get(key);
            }
            list.add(str);
        }
        return  result;


    }
    public String count(String str) {
        int[] bit = new int[26];
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            bit[c -'a'] ++;
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < 26; i++) {
            char c = (char)('a' + i);
            for (int j = 0; j < bit[i]; j++) {
                stringBuilder.append(c);
            }

        }
        return stringBuilder.toString();
    }
}