力扣：字母异位词问题总结（242、49）

超、凢脫俗 2023-01-19 08:27 1阅读 0赞

# 一、字母异位词 #

如果2个字符串(仅由小写字母构成)由同一字母集组成，即为字母异位词。

> 扩展：如果2个字符串由同一unicode字符集组成，即为字母异位词。  
> PS：目前，字母异位词相关的力扣题只涉及小写字母。

# 二、力扣题 #

## 1. [242. 有效的字母异位词][242.] ##

*  通解

class Solution {
        
        public boolean isAnagram(String s, String t) {
        
            char[] tmpS = s.toCharArray();
            Arrays.sort(tmpS);
            s = String.valueOf(tmpS);
            char[] tmpT = t.toCharArray();
            Arrays.sort(tmpT);
            t = String.valueOf(tmpT);
            return s.equals(t);
        }
    }

> 将2个字符串分别转为字符数组，对其进行排序后转为字符串，如果2个字符串相同，即为字母异位词。

*  另一种解法

class Solution {
        
        public boolean isAnagram(String s, String t) {
        
            int[] table = new int[26];
            for(char c : s.toCharArray())
                table[c - 'a']++;
            for(char c : t.toCharArray())
                table[c - 'a']--;
            for(int i = 0; i < 26; i++) {
        
                if(table[i] != 0)
                    return false;
            }
            return true;
        }
    }

> 这种解法仅限于字符串由小写字母组成。

## 2. [49. 字母异位词分组][49.] ##

*  AC代码

class Solution {
        
        public List<List<String>> groupAnagrams(String[] strs) {
        
            Map<String, List<String>> map = new HashMap<>();
            for(int i = 0; i < strs.length; i++) {
        
                char[] str = strs[i].toCharArray();
                Arrays.sort(str);
                String key = new String(str);
                List<String> list = map.getOrDefault(key, new ArrayList<>());
                list.add(strs[i]);
                map.put(key, list);
            }
            return new ArrayList<List<String>>(map.values());
        }
    }

> 本题是对上文`242`的扩展：如果若干字符串(记为value)为字母异位词，那么它们排序后一定是相同的字符串(记为key)，即构成了映射关系：\[key, value\]。

## 三、总结：排序是解决字母异位词的关键 ##

[242.]: https://leetcode-cn.com/problems/valid-anagram/
[49.]: https://leetcode-cn.com/problems/group-anagrams/