编程练习-字母异位词分组

又很久没有做做题了，哎……

题目-LeetCode字母异位词分组

给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

示例:

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

说明：

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

分析

这个题难度定位为中等，个人感觉难度中等有点夸张了。只要把题目和示例看一下就应该知道思路了。

1. 归入一组的字符串组成字母相同，只是顺序不一样而已，因此进行一次排序就好了，相同组的字符串都是同一个字符串形式了，比如示例中的第一组，排序后为`aet`。
2. 最后用一个map做存储结构，因为HashMap的key是不重复的，用排好序的字符串作为key，value当然是list啦。

思路：

实现（java）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
/**
 * @ClassName: GroupAnagrams
 * @Author: fanjiajia
 * @Date: 2019/5/11 下午3:09
 * @Version: 1.0
 * @Description: 给定一个字符串数组，将字母异位词组合在一起。
 *               字母异位词指字母相同，但排列不同的字符串。
 */
public class GroupAnagrams {

    public static void main(String[] args) {
        GroupAnagrams g = new GroupAnagrams();
        String[] strs = {"eat", "tea", "tan", "ate", "nat", "bat"};
        g.groupAnagrams(strs);
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        /**
         * 1 保存原始值, 此处不能直接:tempStrs = strs(java参数传递问题)
         */
        String[] tempStrs = new String[strs.length];
        for(int k = 0; k < strs.length; k++) {
            tempStrs[k] = strs[k];
        }
        /**
         * 2 原始的字符串数组中每个字符串按字母排序
         */
        for(int i = 0; i < strs.length; i++){
            char[] arr = strs[i].toCharArray(); // 转为字符数组
            Arrays.sort(arr);
            strs[i] = String.valueOf(arr);
        }
        /**
         * 3 整理判断
         */
        HashMap<String, List<String>> map = new HashMap<>();
        for(int j = 0; j < tempStrs.length; j++) {
            if(map.containsKey(strs[j])) {
                map.get(strs[j]).add(tempStrs[j]);
            }else {
                List<String> list = new ArrayList<>();
                list.add(tempStrs[j]);
                map.put(strs[j], list);
            }
        }
        // 取出map的值
//        System.out.print(new ArrayList(map.values()));
        return new ArrayList(map.values());
    }
}

这里排序没有重写方法，直接使用Arrays.sort(arr);即可。
需要对原始的字符串数组进行备份，因为排序会改变原有的字符串数组中的元素。备份时，不能直接使用=进行复制，java参数传递是值传递，这里传递的是strs数组的地址，那么=号直接操作的结果是tempStrs同样指向了原始数组strs，排序一样被改变，这也是浅复制和深复制的问题。
最后

此致，敬礼