Leetcode题库-字母异位词分组（java语言版）

题目描述：

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

示例:

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

说明：

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

这道题和那一道有效的字母异构词，相似，不过这个是字符串数组，那个是两个字符串比较。有效的字母异构词博客：https://blog.****.net/weixin_37850160/article/details/88557013

这道题有两种思路，

第一种：就是将字符数组中的每个元素，声明为字符数组，然后排序，如果两个排序后的元素相同则证明是字母异构词，不相同则不是，是字母异构词就将词加入map，键为排序后的字符串，值为列表。最后将map的值放到大列表啊中输出即可。

第二种：这种思路借鉴了官方的解答，觉得很巧妙，就写一下。声明一个26个字符的空数组，然后将字符串数组中的每个元素出现的次数和位置放到这个空数组中，然后将这个空数组作为键放入map中，当再次遇到次数和位置都想同的元素，则证明是异构词，就将词加入list，最后输出map的值即可。

代码如下：

第一种方法：

     String str[] = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
//           第一种方法，排序数组加map存储
           Map<String,List<String>> map = new HashMap <> (  );
           List <List <String>> lists =new ArrayList <> (  );
           for (int i =0;i<str.length;i++){
               char ch[] = str[i].toCharArray ();
//        重点在于排序,转换为字符数组排序
               Arrays.sort ( ch );
//               将char数组类型转为字符串
               String s = String.valueOf(ch);
//               每当出现一个新的字母易位词(map没有对应键)，就往 ret 中添加一个 list，同时往哈希表中添加该字母易位词
               if (!map.containsKey ( s )){
//                   排序后的字符串作为键值。
                   map.put ( s, new ArrayList() );
               }
//               哈希表中添加该字母易位词（对应的键添加对应的未排序的值）
               map.get ( s ).add ( str[i] );
           }
           for (List list:map.values ()){
                lists.add ( list );
           }
           System.out.println(lists);

执行结果：

Leetcode题库-字母异位词分组（java语言版）

执行用时：

Leetcode题库-字母异位词分组（java语言版）

第二种方法：

    第二种方法计数(借鉴答案中的思路):当且仅当它们的字符计数（每个字符的出现次数）相同时，两个字符串是字母异位词。
        Map<String,List> map = new HashMap <> (  );
//        我们可以将每个字符串 s 转换为字符数 count，由26个非负整数组成，表示a，b，c 的数量等。我们使用这些计数作为哈希映射的基础。
        int count[] = new int[26];
        for (String s :str){
//            用0填充这个数组
            Arrays.fill ( count,0 );
            char ch[] = s.toCharArray ();
            for (char c:ch){
//          c-'a'作为每个字符出现在count数组中的索引值('a'=65.其余字符减去'a',得到1-26的索引值).
                count[c-'a']++;
            }
            StringBuilder sb = new StringBuilder (  );
//            我们的字符数 count 的散列化表示将是一个用 **＃** 字符分隔的字符串
            for (int i=0;i<26;i++){
                sb.append ( '#' );
                sb.append (count[i] );
            }
            String key = sb.toString ();
//            sb=#1#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0
//            用这个每个字符出现的次数作为键,空列表作为值.当不存在时,也就是,新的字符串时,添加进map,值为空列表
            if (!map.containsKey (key  )){
                map.put ( key ,new ArrayList (  ));
            }
//            对键对应的值(列表)添加元素,此时键相同,直接添加对应元素进入,不相同,则将值添加进<新建>对应的空列表中等待下一个重复的键的元素(相同的字母异位词).
            map.get ( key ).add ( s );
        }
        System.out.println(map);
        System.out.println(new ArrayList<> (map.values ()  ));

执行结果：

Leetcode题库-字母异位词分组（java语言版）

执行用时：

Leetcode题库-字母异位词分组（java语言版）

总结，这道题设计的很巧妙，第一种方法，排序后比较很多人能想到，但第二种方法，官方给的很巧妙。这种声明空数组的方法值得我去学习，用空数组保存对应索引元素出现的次数。很棒的一种方法。

2019-3-26

Leetcode题库-字母异位词分组（java语言版）

相关推荐