LeetCode热题100（八）—— 438.找到字符串中所有字母异位词

• 你好，我是杨十一，一名热爱健身的程序员
• 在Coding的征程中，不断探索与成长
• LeetCode热题100——刷题记录（不定期更新）
  此系列文章用于记录我在学习 LeetCode热题100 过程中的总结和收获
  愿与诸君共同探讨，在代码世界里携手共进，攻克难题，提升自我

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串。
返回这些子串的起始索引。不考虑答案输出的顺序。
字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。
示例 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" 的异位词。
提示:
        1 <= s.length, p.length <= 3 * 104
        s 和 p 仅包含小写字母

代码实现

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int sLen = s.length();
        int pLen = p.length();
        if (sLen < pLen)
            return result;

        int[] pArray = new int[26];
        int[] sArray = new int[26];

        for (int i = 0; i < pLen; i++) {
            pArray[p.charAt(i) - 'a']++;
            sArray[s.charAt(i) - 'a']++;
        }
        if (Arrays.equals(pArray, sArray)) {
            result.add(0);
        }

        for (int i = 0; i < sLen - pLen; i++) {
            sArray[s.charAt(i) - 'a']--;
            sArray[s.charAt(i + pLen) - 'a']++;
            if (Arrays.equals(pArray, sArray)) {
                result.add(i + 1);
            }
        }

        return result;
    }

}

思路解析

1. 输入：两个字符串 s p 在s中查找p的异位词
2. 输出：异位词起始位置索引集合
3. 思路：双指针 & 异位词特性
   • 双指针：左右指针定位子串起始和结束位置
   • 异位词特性：
     • 长度一致
     • 所使用的字符一致
     • 所使用的字符顺序可以不一致
     • 举例 abc acb bca bac cab cba 互为异位词
   • coding思路
     • 快速失败，若 s.length < p.length 不满足异位词第一条特性 s 的子串不能与 p 构成异位词
     • 滑动窗口：左右指针 [L,R] 间距固定位置 p.length 逐次向后遍历字符串 s
     • 异位词判定：
       • 使用数组int[26]记录子串的各个字符数量（题目描述只包含26个小写字母）
         • 遍历过程中，左右指针同步向右移动，每移动一位，数组中左指针字符数量减一，右指针字符数量加一
         • 如果字符不固定，考虑使用 Map<Character, Integer> 记录出现的字符和出现的次数
       • 判断子串字符与待判定字符串 p 的字符数量是否一致
         • 判断子串字符数量数组与 p 字符数量数组是否一致
         • 判断数组是否一致，工具类 Arrays.equals()
           

• 你好，我是杨十一，一名热爱健身的程序员
• 在Coding的征程中，不断探索与成长
• LeetCode热题100——刷题记录（不定期更新）
  此系列文章用于记录我在学习 LeetCode热题100 过程中的总结和收获
  愿与诸君共同探讨，在代码世界里携手共进，攻克难题，提升自我