LeetCode49. 字母异位词分组 JAVA

迷南。 2022-12-08 12:56 166阅读 0赞

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

示例:
    
    输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
    输出:
    [
      ["ate","eat","tea"],
      ["nat","tan"],
      ["bat"]
    ]
    说明：
    
    所有输入均为小写字母。
    不考虑答案输出的顺序。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/group-anagrams
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：  
1、利用map来记录异位词所属的list  
2、对每一个字符串进行排序，排序后的结果记录进map的key值  
如果map中有该key值，则字符串加入该key值对应的value中list；  
如果map中没有该key值，新建一个list，并将字符串和list的映射添加进map中。  
3、注意字符串排序方法

class Solution {
        
        public List<List<String>> groupAnagrams(String[] strs) {
        
            Map<String,List<String>> map=new HashMap<>();
            List<List<String>> res=new ArrayList<>();
            for(String s:strs)
            {
        
                String tmp=sort(s);
              //  Arrays.sort(tmp);
                if(map.containsKey(tmp))
                {
        
                    map.get(tmp).add(s);
                }
                else
                {
        
                    List<String> list=new ArrayList<>();
                    list.add(s);
                    res.add(list);
                    map.put(tmp,list);
                }
            }
            return res;
        }
         public static String sort(String str){
        
             //利用toCharArray可将字符串转换为char型的数组
             char[] s1 = str.toCharArray();
             for(int i=0;i<s1.length;i++){
        
                 for(int j=0;j<i;j++){
        
                     if(s1[i]<s1[j]){
        
                         char temp = s1[i];
                         s1[i] = s1[j];
                         s1[j] = temp;
                     }
                 }
             }
             //再次将字符数组转换为字符串，也可以直接利用String.valueOf(s1)转换
             String st = new String(s1);
             return st;
         }
    }