leetcode-异位词问题总结

xkge / 2023-07-31 / 原文

总结一下leetcode中遇见的异位词问题：

242. 有效的字母异位词 - 力扣（LeetCode）

本题是异位词题目中最基础的，有两种方法可以轻松解决：

1. 排序法，时间复杂度O(n log n):

class Solution {
    //排序解决
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        char[] sArr = s.toCharArray();
        char[] tArr = t.toCharArray();
        Arrays.sort(sArr);
        Arrays.sort(tArr);
        return String.valueOf(sArr).equals(String.valueOf(tArr)) ? true : false;
    }
}

2. 哈希表法，时间复杂度O(n)：

class Solution {
    //哈希表解法
    //时间复杂度O(n)
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()) return false;
        //由于只有小写字母，可以直接用一个数组作为哈希表，效率更好
        int[] map = new int[26];
        //遍历s的字符
        for(char c : s.toCharArray()){
            map[c - 'a']++;
        }
        //遍历t的字符
        for(char c : t.toCharArray()){
            map[c - 'a']--;
        }
        //判断map中是否有非零元素，如果有则返回false,否则true
        for(int i : map){
            if(i > 0) return false;
        }
        return true;
    }
}

唯一需要注意的一点是，当元素个数已知且较少的时候，数组本身也可以作为一个哈希表使用，由于题目指定单词中只有小写字母，我们直接用一个数组作为哈希表，这会比使用内置HashMap效率更高。

49. 字母异位词分组 - 力扣（LeetCode）

这道题采用哈希表复杂度最好：

import java.util.*;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for(String s : strs){
            char[] sArr = s.toCharArray();
            Arrays.sort(sArr);
            //注意这个String的构造方法
            String key = new String(sArr);
            List<String> ls = map.getOrDefault(key, new ArrayList<>());
            ls.add(s);
            map.put(key, ls);
        }
        //注意ArrayList的这个构造方法
        return new ArrayList<List<String>>(map.values());
    }

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