【每日一题】day3 @剑指offer 字符串中的变位词

文章目录

    • 题目描述
    • 问题分析
    • 方法一: 双指针法
    • 方法二: 利用滑动窗口

题目描述

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

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

示例 1:

输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).

示例 2:

输入: s1= “ab” s2 = “eidboaoo”
输出: False

问题分析

首先是对变位词的理解,那么什么是变位词呢?其实就是一个字符串的好几种排列方式的字符串。

例如说:原字符串为:post 那么它的变位词就有:stop tsop ostp ……

本题是让判断长的字符串s中是否有短字符串t的变位词。

我们的想法是这样的,如果在长字符串s中,有字符和t字符串中出现的字符一样,并且出现的次数相同,那么就说明该字符串中存在变位词。

方法一: 双指针法

具体做法: 因为题目中所说输入的字符串中的字符都是小写,那就是26个英文小写字母,我们加一个长度为26的整形数组,如果在短字符串中出现过的字符,我们在整形数组中进行标记。使用s.charAt(i) - ‘a’,找到它的标记位置,进行加一。把长字符串中的前t.length个字符,也在整形数组中进行标记,进行减一,如果此时的整形数组中的所有元素都为0,那么就说明在长字符串中存在短字符串t的变位词。如果此时还没有,那么继续遍历长字符串。并且每次遍历一个字符,就把这个字符所在的整形数组的标志为加1,并且把 s.charAt(i - t.length) - ‘a’,在整形数组的标志位下标,减一。

图文解释
【每日一题】day3 @剑指offer 字符串中的变位词_第1张图片

主要代码:

class Solution {
    public boolean checkInclusion(String s1, String s2) {
    //使用双指针思想,每次在长字符串中,遍历一个短字符串的长度,在这个短字符串中left 指针指向字符串的头部,right
        //指针指向 字符串的尾部。
        //判断边界条件
        int m = s1.length();
        int n = s2.length();
        if(m > n){
            return false;
        }
        int []array1 = new int[26];
        //初始化
        for(int i = 0;i<m;i++){
            array1[s1.charAt(i) - 'a']++;
            array1[s2.charAt(i) - 'a']--;
        }
        //判断在整个整数遍历数组中,看是否都是0,如果都是0,那么证明当前的长字符串中有短字符串的变位词
        if(isZero(array1) == true){
            return true;
        }
        for(int i = s1.length();i<s2.length();i++){
            array1[s2.charAt(i) - 'a']--;
            array1[s2.charAt(i - s1.length()) - 'a']++;
            if(isZero(array1)){
                return true;
            }
        }
        return false;
    }
    //判断字符串中全部是否为零
    public boolean isZero(int []array){
        for(int i = 0;i<array.length;i++){
            if(array[i] != 0){
                return false;
            }
        }
        return true;
    }
}

方法二: 利用滑动窗口

方法解析: 这种方法需要建立两个标记数组,数组array1还是一个有26个元素的数组,在array1中标记短字符串t中字符在26个英文字母中出现的位置。数组array2也是一个有26个元素的数组。这是滑动窗口的left和right都指向长字符串的第一个字符。并且在array2中标记第一个字符出现的位置。在array2中标记为1,如果此时array2[index] != array1[index] (index表示两个字符串中标记数组的下标)那么就说明第一个字符不是变位词中的字符。然后left++,并且进行循环。如果right - left + 1 == 变位词的字符个数,那么直接返回true,如果把整个长字符串遍历完,都没有找到变位词,那么返回false。

图文解释:

【每日一题】day3 @剑指offer 字符串中的变位词_第2张图片

主要代码:

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        // 使用滑动窗口
        // 如果s1.length < s2.length 那么就返回false
        // 设置两个数组,表示s1中的字符出现的次数,另一个数组表示s2中s1出现的次数
        int m = s1.length();
        int n = s2.length();
        if(m > n){ //如果s1字符串的长度大于s2的长度直接返回false
            return false;
        }
        //建立cnt1数组
        int []cnt1 = new int[26];
        int []cnt2 = new int[26];
        for(int i = 0;i<s1.length();i++){
            cnt1[s1.charAt(i) - 'a']++;
        }
        int left = 0;
        //设置左指针,左指针,和右指针,同时指向0下标对应的元素
        for(int right = 0;right < s2.length();right++){
            //  a b
            //  e i d b a o o o
            //        L R
            // R - L + 1 == m
            //           a  b  c  d  e  f  g  h  i  j
            cnt1     1  1  0  0  0  0  0  0  0  0
            cnt2     0  0  0  0  1  0  0  0  0  0    因为在cnt2[index] > cnt1[index] 所以两个字符不匹配
            //           0  0  0  0  0  0  0  0  1  0
            //           0  0  0  1  0  0  0  0  0  0
            //           0  1  0  0  0  0  0  0  0  0
            //           1  1  0  0  0  0  0  0  0  0  
            int index = s2.charAt(right) - 'a'; 
            cnt2[index]++;
            //如果index在cnt2中指向的字符和index造cnt1中指向的字符串不相同,那么滑动窗口的left向右移动一位,同时
            //把原本在cnt2中新增的1变为0
            while(cnt2[index] > cnt1[index]){
                cnt2[s2.charAt(left) - 'a']--;
                left++;
            }
            if(right - left + 1 == m){
                return true;
            }
        }
        return false;
    }

你可能感兴趣的