当前位置：首页 > article >正文

LeetCode题练习与总结：找到字符串中所有字母异位词--438

article 2024/12/2 8:06:23

一、题目描述

给定两个字符串 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 * 10^4
s 和 p 仅包含小写字母

二、解题思路

首先定义两个数组，分别记录字符串 s 和 p 中每个字符出现的次数。由于字符串只包含小写字母，所以可以使用长度为 26 的数组。
遍历字符串 p，统计每个字符出现的次数，并记录在数组 p_count 中。
使用一个滑动窗口来遍历字符串 s，窗口大小为 p 的长度。在滑动窗口中，统计窗口内每个字符出现的次数，并记录在数组 s_count 中。
每次滑动窗口移动时，比较 s_count 和 p_count 是否相等。如果相等，说明找到了一个异位词，记录当前窗口的起始索引。
继续移动滑动窗口，每次移动时，更新 s_count 数组，直到遍历完字符串 s。
返回所有异位词的起始索引。

三、具体代码

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        if (s == null || s.length() == 0 || p == null || p.length() == 0) {
            return result;
        }

        int[] s_count = new int[26];
        int[] p_count = new int[26];
        int s_len = s.length(), p_len = p.length();

        // 统计 p 中每个字符出现的次数
        for (char c : p.toCharArray()) {
            p_count[c - 'a']++;
        }

        // 使用滑动窗口遍历 s
        for (int i = 0; i < s_len; i++) {
            // 将当前字符加入 s_count
            s_count[s.charAt(i) - 'a']++;

            // 移除窗口最左边的字符
            if (i >= p_len) {
                s_count[s.charAt(i - p_len) - 'a']--;
            }

            // 如果 s_count 和 p_count 相等，说明找到了一个异位词
            if (i >= p_len - 1 && compareArrays(s_count, p_count)) {
                result.add(i - p_len + 1);
            }
        }

        return result;
    }

    // 比较 two arrays 是否相等
    private boolean compareArrays(int[] arr1, int[] arr2) {
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }
}

四、时间复杂度和空间复杂度

1. 时间复杂度

统计字符串 p 中每个字符出现的次数，需要遍历整个字符串 p，这是一个 O(p_len) 的操作，其中 p_len 是字符串 p 的长度。
使用滑动窗口遍历字符串 s，这个操作需要遍历整个字符串 s，这是一个 O(s_len) 的操作，其中 s_len 是字符串 s 的长度。
在每次滑动窗口移动时，都会调用 compareArrays 方法来比较两个数组。由于这两个数组长度固定为 26，所以这个操作的时间复杂度是 O(1)。

因此，总的时间复杂度是 O(p_len) + O(s_len) * O(1) = O(p_len + s_len)。

2. 空间复杂度

使用了两个长度为 26 的数组 s_count 和 p_count 来分别记录字符串 s 和 p 中每个字符出现的次数，所以这部分的空间复杂度是 O(1)，因为这两个数组的长度是常数。
使用了一个列表 result 来存储结果，在最坏的情况下，如果字符串 s 中每个长度为 p_len 的子串都是字符串 p 的异位词，那么这个列表的长度将是 O(s_len)。因此，这部分的空间复杂度是 O(s_len)。

综上所述，总的空间复杂度是 O(1) + O(s_len) = O(s_len)。

五、总结知识点

类定义：定义了一个名为 Solution 的类，这是 Java 中定义类的基本方式。
方法定义：在 Solution 类中定义了一个公共方法 findAnagrams，它接受两个字符串参数 s 和 p，并返回一个整数列表。
条件判断：在方法开始处，使用 if 语句检查输入字符串是否为空或长度为零，这是防御性编程的一种形式，用于避免空指针异常。
数组的声明和使用：声明了两个长度为 26 的整型数组 s_count 和 p_count，用于存储每个字符出现的次数。由于只考虑小写字母，所以数组的大小为 26，对应英文字母表中的字母数量。
字符与整数的转换：通过 char - 'a' 将字符转换为对应的整数索引，这是处理字符计数问题的常用技巧。
循环结构：使用了 for 循环来遍历字符串 p 和 s，以及数组 s_count 和 p_count。
列表的使用：使用了 ArrayList 来存储和返回结果，这是一种动态数组，用于存储找到的异位词的起始索引。
方法调用：在主方法 findAnagrams 中调用了辅助方法 compareArrays 来比较两个数组是否相等。
逻辑运算：在滑动窗口的逻辑中，使用了逻辑与运算符 && 来确保只有在窗口大小等于 p 的长度时才比较两个数组。
辅助方法：定义了一个私有辅助方法 compareArrays，用于比较两个整型数组是否相等，这是代码模块化和复用的体现。
数组索引操作：在滑动窗口中，通过数组索引操作来更新和检查字符计数。
列表添加操作：使用 add 方法将找到的异位词起始索引添加到结果列表中。