第一个异位词的子串

约 739 字大约 2 分钟

2024-11-11

🌳 题目描述：

给定两个字符串 s 和 t，找到 s 中第一个 t 的异位词的子串。

示例 1:
输入: s = "adcabcbabcd", t = "abc"
输出: "cab"
解释:
异位词：两个字符串中出现的字符种类以及各字符出现的次数相同。
起始索引等于 2 的子串是 "cab", 它是 "abc" 的异位词, 且是 s 中第一个出现。

📝思路分析：

由异位词的定义，要在 s 中找到 t 的异位词，需要满足两个条件：

异位词的长度与 t 的长度相等，可以用双指针指定同等长度的窗口作为潜在的异位词所在的区域
定长的窗口内，字符出现的种类和各字符出现的次数要与 t 相同

条件1，不难达到，定义一个左边界 left, 当前访问的字符索引记为 i, 只需判断 i - left + 1 == t.length();

条件2，我们将 t 中出现的字符以及次数存在哈希表里 targetMap, 再创建一个哈希表 windowMap 用来存储字符串 s 当前窗口内字符以及出现的次数，再与 t 中出现的字符次数对比，如果次数相同，则表明有一个字符及其出现的次数匹配成功，计数器 counter ++, 直到匹配的次数达到 t 中字符的种类，也就是 targetMap.size(), 说明 t 中所有的字符均已匹配成功，异位词已找到。

注意当窗口滑动时，最左边的字符 leftChar 会滑出窗口，如果滑出之前，它出现的次数在 targetMap 和 windowMap 相等，需要 counter --，表明有一个字符即将从匹配进入未匹配状态。

💻代码：

Java

public String findFirstAnagram(String s, String t) {
    if (s == null || t == null || s.length() < t.length()) {
        return "";
    }

    Map<Character, Integer> targetMap = new HashMap<>();
    Map<Character, Integer> windowMap = new HashMap<>();
    for (int i = 0; i < t.length(); i++) {
        targetMap.put(t.charAt(i), targetMap.getOrDefault(t.charAt(i), 0) + 1);
    }

    int left = 0;
    int count = 0;

    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (targetMap.containsKey(c)) {
            windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);
            if (windowMap.get(c).equals(targetMap.get(c))) {
                count++;
            }
        }

        if (i - left + 1 == t.length()) {
            if (count == targetMap.size()) {
                return s.substring(left, left + t.length());
            }
            char leftChar = s.charAt(left);
            if (targetMap.containsKey(leftChar)) {
                if (targetMap.get(leftChar).equals(windowMap.get(leftChar))) {
                    count--;
                }
                windowMap.put(leftChar, windowMap.getOrDefault(leftChar, 0) - 1);
            }
            left++;
        }
    }

    return "";
}

🚵🏻复杂度分析：

n 为 s 的长度，m 为 t 的长度

时间复杂度: O(n), t 遍历一遍，s 至多遍历两遍，时间复杂度为 O(2n + m), 又因为 m <= n, 所以时间复杂度为 O(n)

空间复杂度: O(k), k 为字符集中的个数, targetMap 存 <key, value> 的个数为 t 中出现不同字符的种类，通常如果只出现英文字母，空间复杂度可记为 O(1)

第一个异位词的子串

⭐ 题目日期：

🌳 题目描述：

🕵🏽 面试评估：

🧗 难度系数：

📝思路分析：

💻代码：

🚵🏻复杂度分析：