【必备算法】字符串（异位词问题）：LeetCode题 242. 有效的字母异位词，49. 字母异位词分组，438. 找到字符串中所有字母异位词

野性酷女 2022-12-15 12:50 172阅读 0赞

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

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

**示例 1:**

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

**示例 2:**

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

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

**进阶:**  
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

### 解法一：双重循环 ###

*  思路：很简单，就是判断两个字符串的组成是否完全相同。落实在代码上就是嵌套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. 字母异位词分组²][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());
    }

## [438. 找到字符串中所有字母异位词²][438.] ##

给定一个字符串 **s** 和一个非空字符串 **p**，找到 **s** 中所有是 **p** 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 **s** 和 **p** 的长度都不超过 20100。

**说明：**

*  字母异位词指字母相同，但排列不同的字符串。
 *  不考虑答案输出的顺序。

**示例 1:**

输入:
    s: "cbaebabacd" p: "abc"
    
    输出:
    [0, 6]
    
    解释:
    起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
    起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

**示例 2:**

输入:
    s: "abab" p: "ab"
    
    输出:
    [0, 1, 2]
    
    解释:
    起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
    起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
    起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

### 解法一：枚举法 ###

*  思路：很粗暴，就是枚举出s的所有长度为p的连续子串，然后判断是否异位词。
 *  复杂度：
    
     *  Time：O(n)
     *  Space：O(m)，要创建一个p长度的数组

public List<Integer> findAnagrams(String s, String p) {
        
            if (s.length() < p.length()) return new ArrayList<Integer>();
            List<Integer> res = new ArrayList<>();
        	// 1.模板数组
            char[] template = p.toCharArray();
        	// 注：数组排序是为了后面与子串们进行比较
            Arrays.sort(template);
        	// 2.枚举所有p长度的连续子串
            for (int i = 0; i <= s.length() - p.length(); i++) {
        
                // 子串数组
                char[] sub = s.substring(i, i + p.length()).toCharArray();
                Arrays.sort(sub); // 比较的核心：排序！！
                // 注：数组进行比较用Arrays.sort
                if (Arrays.equals(sub, template))
                    res.add(i);
            }
            return res;
        }

### 解法二：滑动窗口\* ###

public List<Integer> findAnagrams(String s, String p) {
        
            // 用于返回字母异位词的起始索引
            List<Integer> res = new ArrayList<>();
            // 用 map 存储目标值中各个单词出现的次数
            HashMap<Character, Integer> map = new HashMap<>();
            for (Character c : p.toCharArray()) map.put(c, map.getOrDefault(c, 0) + 1);
            // 用另外一个 map 存储滑动窗口中有效字符出现的次数
            HashMap<Character, Integer> window = new HashMap<>();
            int left = 0; // 左指针
            int right = 0; // 右指针
            int valid = p.length(); // 只有当 valid == 0 时，才说明 window 中包含了目标子串
            while (right < s.length()) {
        
                // 如果目标子串中包含了该字符，才存入 window 中
                if (map.containsKey(s.charAt(right))) {
        
                    window.put(s.charAt(right), window.getOrDefault(s.charAt(right), 0) + 1);
                    // 只有当 window 中该有效字符数量不大于map中该字符数量，才能算一次有效包含
                    if (window.get(s.charAt(right)) <= map.get(s.charAt(right))) {
        
                        valid--;
                    }
                }
                // 如果 window 符合要求，即两个 map 存储的有效字符相同，就可以移动左指针了
                // 但是只有二个map存储的数据完全相同，才可以记录当前的起始索引，也就是left指针所在位置
                while (valid == 0) {
        
                    if (right - left + 1 == p.length()) res.add(left);
                    // 如果左指针指的是有效字符,需要更改 window 中的 key 对应的 value
                    // 如果 有效字符对应的数量比目标子串少，说明无法匹配了
                    if (map.containsKey(s.charAt(left))) {
        
                        window.put(s.charAt(left), window.get(s.charAt(left)) - 1);
                        if (window.get(s.charAt(left)) < map.get(s.charAt(left))) {
        
                            valid++;
                        }
                    }
                    left++;
                }
                right++;
            }
            return res;
        }

[242.]: https://leetcode-cn.com/problems/valid-anagram/
[49.]: https://leetcode-cn.com/problems/group-anagrams/
[438.]: https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/