leetcode 438. Find All Anagrams in a String | 438. 找到字符串中所有字母异位词（Java）

柔情只为你懂 2022-09-04 05:50 157阅读 0赞

## 题目 ##

[https://leetcode.com/problems/find-all-anagrams-in-a-string/][https_leetcode.com_problems_find-all-anagrams-in-a-string]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

#### 方法1：尝试构造一种“与顺序无关的哈希” ####

##### 思考 #####

是否可以构造**顺序无关的哈希**？例如，我们希望 aabc 与 bcaa 的哈希值相同。

##### 思路 #####

找到一种映射方式，使得在保证每一个字母都出现在 set 中的情况下，让不同字母具有不同的贡献度，计算每个字母的贡献度求 sum，从而实现“**不同数量的字母组成的不同序列具有唯一 sum，相同数量的字母组合具有相同 sum，结果与顺序无关**”。

##### 结果 #####

上述“映射方式”可以被证明是不存在的。  
我仍然用代码实现了一遍，没想到 AC 了。方法有逻辑问题，但是通过了所有的测试用例。  
例如，a到z都包含在字符串中的情况下，只要找到 a+b = c+d，就是反例。

##### 反例 #####

> a aac bcdefghijklmnopqrstuvwxyz  
> a bbb bcdefghijklmnopqrstuvwxyz  
> 其中，中间部分的 a+a+c = b+b+b

##### 证伪 #####

以下步骤可以证明 **一定存在反例**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public List<Integer> findAnagrams(String s, String p) { 
            int target = 0;
            Set<Character> set = new HashSet<>();
            for (int i = 0; i < p.length(); i++) { 
                target += Math.pow(2, p.charAt(i) - 'a');
                set.add(p.charAt(i));
            }
            
            ArrayList<Integer> list = new ArrayList<>();
            if (s.length() < p.length()) return list;
            int cur = 0;
            for (int i = 0; i < p.length(); i++) { 
                cur += Math.pow(2, s.charAt(i) - 'a');
            }
            int i;
            for (i = 0; i < s.length() - p.length(); i++) { 
                if (cur == target && set.contains(s.charAt(i))) list.add(i);
                cur -= Math.pow(2, s.charAt(i) - 'a');
                cur += Math.pow(2, s.charAt(i + p.length()) - 'a');
            }
            if (cur == target && set.contains(s.charAt(i))) list.add(i);
    
            return list;
        }
    }

手动构造的一个最简单的反例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]

#### 方法2： ####

定义两个数组：

*  target\[26\] 数组，统计目标窗口内每个字母的个数。
 *  cur\[26\] 数组，统计当前滑窗内每个字母的个数。
 *  dif 为两数组之间个数不相等的字母总数。

先固定好窗口大小，每次双指针前进1。

然后在固定窗口大小的基础上，观察操作前后的变化：

*  如果操作前cur=dif，则dif+1
 *  如果操作后cur=dif，则dif-1

class Solution { 
        public List<Integer> findAnagrams(String s, String p) { 
            int[] target = new int[26];
            int dif = 0;
            for (int i = 0; i < p.length(); i++) { 
                if (target[p.charAt(i) - 'a'] == 0) dif++;
                target[p.charAt(i) - 'a']++;
            }
    
            ArrayList<Integer> list = new ArrayList<>();
            if (s.length() < p.length()) return list;
            int[] cur = new int[26];
            for (int i = 0; i < p.length(); i++) { 
                if (cur[s.charAt(i) - 'a'] == target[s.charAt(i) - 'a']) dif++; // 本来就相等
                cur[s.charAt(i) - 'a']++;
                if (cur[s.charAt(i) - 'a'] == target[s.charAt(i) - 'a']) dif--; // 加完之后相等了
            }
    
            int L;
            for (L = 0; L < s.length() - p.length(); L++) { 
                if (dif == 0) list.add(L);
                int R = L + p.length();
                // 删i
                if (cur[s.charAt(L) - 'a'] == target[s.charAt(L) - 'a']) dif++; // 本来就相等
                cur[s.charAt(L) - 'a']--;
                if (cur[s.charAt(L) - 'a'] == target[s.charAt(L) - 'a']) dif--; // 减完之后相等了
                // 加j
                if (cur[s.charAt(R) - 'a'] == target[s.charAt(R) - 'a']) dif++; // 本来就相等
                cur[s.charAt(R) - 'a']++;
                if (cur[s.charAt(R) - 'a'] == target[s.charAt(R) - 'a']) dif--; // 加完之后相等了
            }
            if (dif == 0) list.add(L);
    
            return list;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]

[https_leetcode.com_problems_find-all-anagrams-in-a-string]: https://leetcode.com/problems/find-all-anagrams-in-a-string/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/5baf5f4ea9284866a21e5c550e60af0e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/805c5d35c9df47d688552c007e30ee2e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 2]: /images/20220829/870df4911a3b456bbc3f305651b72734.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 3]: /images/20220829/d6f4e6f22d8842ad97a50bb4c17b9fae.png