剑指 Offer II 014 字符串中的变位词

发表于

「这是我参与11月更文挑战的17天，活动详情查看：2021最后一次更文挑战」

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ini复制代码示例 1：

输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例 2：

输入: s1= "ab" s2 = "eidboaoo"
输出: False
 

提示：

1 <= s1.length, s2.length <= 104
s1 和 s2 仅包含小写字母

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/MP…

思路

  • 首先异位词的题目，一般都可以空间换时间去解决
    • 所以我们可以使用哈希表去解决
    • 但是题目中说到是小写字母，所以我们用固定大小的26位数组去标记计数
  • 我们用ab和cba来举例
    • 当出现ab和abc这样的样例我们是最好解决的
    • 只要对应位置在数组中加一后再减一，就可以得出ab是abc的子序列
    • 所以我们代码中第一次的判断就是做一个这样的情况
    • 面对ab和cba的情形，我们使用双指针去解决
    • 最开始是下面的情形

image.png

  • 然后对应字符串2的情况是下图所示

image.png

  • 将s1的字符串为滑动窗口的长度，每次进行扫描

image.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
java复制代码class Solution {
    public boolean checkInclusion(String s1, String s2) {
        boolean flag = true;
         if (s2.length() < s1.length()) {
             return false;
         }
         int[] counts = new int[26];
         for (int i = 0; i < s1.length(); i++) {
             counts[s1.charAt(i) - 'a']++;
             counts[s2.charAt(i) - 'a']--;
         }
         if (check(counts)) return true;

         for (int i = s1.length(); i < s2.length(); i++) {
             counts[s2.charAt(i) - 'a']--;
             counts[s2.charAt(i - s1.length()) - 'a']++;
             if (check(counts)) return true;
         }
        
         return false;      
    }
    boolean check(int[] arr) {
        for (int i : arr) {
            if (i != 0) return false;
        }
        return true;
    }
}

下一篇我们会去介绍，这道题的变种题，这篇主要使用双指针+标记法📌

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%