【数据结构】散列表：LeetCode题（一）242. 有效的字母异位词，49. 字母异位词分组

在看散列表相关LeetCode题之前，先放个传送门【数据结构】散列表，从特性分析到散列冲突再到应用总结…

242. 有效的字母异位词¹

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

说明:
你可以假设字符串只包含小写字母。

异位词：组成相同，顺序不同

解法一：双重循环

• 思路：很简单，就是判断两个字符串的组成是否完全相同。落实在代码上就是嵌套for循环：外层遍历s，内层遍历t寻找与s当前字符相同的字符，若存在就将t中相同字符置为空（注：这里用 replaceFirst）
• 复杂度
  • Time：O(m*n)，m是s的长度，n是t的长度
  • Space：O(1)

public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        boolean res = true;
    
    	// 遍历s
        for (int i = 0; i < s.length(); i++) {
            // 遍历t
            for (int j = 0; j < t.length(); j++) {
                res = false;
                if (s.charAt(i) == t.charAt(j)) {
                    res = true;
                    // replace是替换全部，所以这里用replaceFirst
                    // replaceFirst的第一个参数是String，所以要String.valueOf
                    // 注：一定要再 t = t.re，因为String是不可变的
                    t = t.replaceFirst(String.valueOf(t.charAt(j)),"");
                    break;
                }
            }
            if (!res) break;
        }
        return res;
}

解法二：散列表

• 思路：记录每个字符的出现次数，这其实是一种K-V思想，所以可以用到散列表
  • 因为总共才26个字母，所以一个数组（alph[26]）就够了。其中，key是数组索引，v是字符出现次数的计数
  • 当s中有某个字符时 alph[s.charAt(i) - ‘a’]++，而当t中有某个字符时 alph[t.charAt(i) - ‘a’]–，最后看aplh中是否所有字符的计数为0
• 复杂度
  • Time：O(n)
  • Space：O(1)，因为只有26个字母，所以数组的大小与数据规模无关

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

这里再强调一下，散列表一般用与需要K-V思想的场景。落实在代码上分为两种情况：当散列表只需要保存value时，用数组就行；而当要同时保存key和value时，一般用HashMap。

49. 字母异位词分组²

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

示例:

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

说明：

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

解法：散列表（HashMap）

• 思路：由于所有 list 的字母组成相同，所以本题其实也包含了 K-V 的思想，可以用到散列表
  • 这里可以使用HashMap，key是String表示公有字符，value是List表示key组成的不同字符串
  • 若当前字符串与key相同组成，则取出key的List然后add
  • 若不存在，则将这个key放入map，并新建一个List
• 细节
  • key：必须要将字符串，先化为数组进行排序（toCharrArray)，然后再化为字符串作为key(String.valueOf)
  • 在返回List<List>时，new ArrayList<List>(map.values())

 public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>(); 
        for (int i = 0; i < strs.length; i++) {
            // string -> array -> string
            char[] c = strs[i].toCharArray();
            Arrays.sort(c);
            String key = String.valueOf(c);
            // 如果包含这个key，就将当前字符串加入相应list
            if (map.containsKey(key)) {
                map.get(key).add(strs[i]);
            // 如果不包含，就新建一个list，然后放入当前字符串
            }else {
                List<String> l = new ArrayList<>();
                l.add(strs[i]);
                map.put(key,l);
            }
        }
        // 注：这里要用map的value构造一个ArrayList
        return new ArrayList<List<String>>(map.values());
}

代码优化，优化了if-else，代码更简洁可读：

public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] c = strs[i].toCharArray();
            Arrays.sort(c);
            String key = String.valueOf(c);
            // 若不存在直接就新建一个空List
            if (!map.containsKey(key)) 
                map.put(key, new ArrayList<String>());   
            // 不管key有没有，都取出然后加入其List
            map.get(key).add(strs[i]);
        }
        return new ArrayList<List<String>>(map.values());
}