字符串的排列(双指针)

作者:神秘网友 发布时间:2021-02-12 16:50:04

字符串的排列(双指针)

先给题
给定两个字符串s1和s2,写一个函数来判断 s2 是否包含 s1的排列。

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

示例1:

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

示例2:

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

注意:

输入的字符串只包含小写字母
两个字符串的长度都在 [1, 10,000] 之间

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


今天第一次,没有看题解做出来了,时间和内存还都可以的情况下。继续加油!

1.暴力破解

以后就不谈暴力破解了,一般这样的题暴力破解都超时

2.自己想的

说一说自己的想法

(1)总体思想

第一眼看到这个字符串匹配的问题,就想到了滑动窗口(双指针),最近做这样的题蛮多的。
(看了题解才知道我用的是双指针,双指针和滑动窗口并不是一摸一样的,具体区别可以看https://blog.csdn.net/WizardWXY/article/details/113703470,感觉讲的蛮好的)
我们先来理解一下题,题的意思是我们要判断s2中是否存在一个与s1等长度的子数组,元素种类与元素个数与s1完全相同。有就返回1,没有就返回0.
(一开始我是按照顺序也一致做的,不管正序或者逆序。但后来发现理解错题了。)
所以,我们要想办法来记录一下子字符串的的元素状况,我们开辟一个长度为26的数组来记录个元素的数量。这个数组来记录s1字符串元素的情况。当右指针移动时,判断这个元素个数是否为0,不为0代表目前子字符串的元素种类和个数都没问题,如果为0,就表明这个元素要么不存在,要么前面存在这个元素的数量已经超过了s1中的,这时候我们就要左指针移动,并且要再把左边移动出来的元素再记录进去。
那么记下来的问题就是如何判断查找出符合的情况以及左指针根据什么条件移动。(这也是最难的两个点)

(2)我们先来谈一谈左指针如何移动。

左指针一旦移动,就代表了当前子字符串的元素种类或者数目不符合要求,左指针需要移动,那么左指针移动到什么地步,子字符串就符合了
极限的情况,我们遇到了一个s1根本不存在的元素,那么此时子字符串肯定不符合要求了,让left和right移动到这个元素的后面重新开始。
而如果我们遇到的元素是前面出现的元素,只是数量达不到要求,那么左指针只要移动到与该元素相同的那个元素的后面,我们就可以不用再移动了,此时子字符串肯定符合要求。
根据上面的两种情况,我们可以得出,只要右指针指向的元素的可用值为0,我们左指针就要一直移动,直到左指针达到右指针的位置。当左指针不再移动时,再来判断右指针指向元素是否大于0(因为右指针指向的元素不存在,那么左指针就移动到右指针的位置,所以还需要在判断一下数值),大于0,就说明这个元素是存在于s1的,记录影响值,=0,就说明这个元素不存在,左指针继续移动一位,跳过这个元素。


(3)再来谈一下判断有无的条件


一开始我是这么想的,当这个记录数值的26位数组所有值都为0的时候,就代表着元素全部用完了,但这样太费时了。
所以我们来找另一种判断的方法。
假设一开始我们就没遇到不符合的元素,那么右指针一直移动,当这个子数组元素情况与s1相等时,此时我们就可以判断它是符合条件的。这样的话如果我们遇到不符合的元素,那么此时右指针减去左指针+1 一定是小于等于s1的长度的。
根据上述假设,我们就可以知道,当判断后如果右指针减去左指针+1(即当前子数组长度)达到了s1的长度,那么我们就可以说存在符合题意的子数组了。


(4)理解完了就上代码

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
    int left = 0, right = 0;
    vectorint v(26, 0);
    for (int i = 0; i  s1.length(); i++)
        v[(int)s1[i] - 97]++;
    while (right  s2.length()) {
        if (v[(int)s2[right] - 97]  0) 
            v[(int)s2[right] - 97]--;
        else
        {
            while (v[(int)s2[right] - 97] == 0  left  right) {
                v[(int)s2[left] - 97]++;
                left++;
            }
            if (v[(int)s2[right] - 97]  0) 
                v[(int)s2[right] - 97]--;
            else
                left++;
        }
        right++;
        if (right - left == s1.length()) 
            return 1;
        
    }
    return 0;
}
};
View Code

3.题解

题解有两种,一种是滑动窗口,一种是双指针(和我想的一摸一样),所以在这里我们就来说滑动窗口。
其实思路差不很多,我们依然是开辟数组来记录元素的状况。只不过这次我们是来记录两个子数组的情况。
要想符合题意,s2的子数组长度肯定是s1的长度,所以只要两个数组的元素情况相同,我们就可以返回1。左指针跟着右指针移动,窗口的长度固定不变。

官方题解还对这个方法进行了优化,我们可以只开辟一个数组来记录情况,这个数组用来记录上述方法中用来记录元素状况的两个数组的差,判断条件我们可以用一个diff来记录他们的不同值,当差不为0,就让diff++,只要diff不为0,那么就不符合。
这是未优化的

 1 class Solution {
 2 public:
 3     bool checkInclusion(string s1, string s2) {
 4         int n = s1.length(), m = s2.length();
 5         if (n  m) {
 6             return false;
 7         }
 8         vectorint cnt1(26), cnt2(26);
 9         for (int i = 0; i  n; ++i) {
10             ++cnt1[s1[i] - 'a'];
11             ++cnt2[s2[i] - 'a'];
12         }
13         if (cnt1 == cnt2) {
14             return true;
15         }
16         for (int i = n; i  m; ++i) {
17             ++cnt2[s2[i] - 'a'];
18             --cnt2[s2[i - n] - 'a'];
19             if (cnt1 == cnt2) {
20                 return true;
21             }
22         }
23         return false;
24     }
25 };
View Code

这是优化的

 1 class Solution {
 2 public:
 3     bool checkInclusion(string s1, string s2) {
 4         int n = s1.length(), m = s2.length();
 5         if (n  m) {
 6             return false;
 7         }
 8         vectorint cnt(26);
 9         for (int i = 0; i  n; ++i) {
10             --cnt[s1[i] - 'a'];
11             ++cnt[s2[i] - 'a'];
12         }
13         int diff = 0;
14         for (int c: cnt) {
15             if (c != 0) {
16                 ++diff;
17             }
18         }
19         if (diff == 0) {
20             return true;
21         }
22         for (int i = n; i  m; ++i) {
23             int x = s2[i] - 'a', y = s2[i - n] - 'a';
24             if (x == y) {
25                 continue;
26             }
27             if (cnt[x] == 0) {
28                 ++diff;
29             }
30             ++cnt[x];
31             if (cnt[x] == 0) {
32                 --diff;
33             }
34             if (cnt[y] == 0) {
35                 ++diff;
36             }
37             --cnt[y];
38             if (cnt[y] == 0) {
39                 --diff;
40             }
41             if (diff == 0) {
42                 return true;
43             }
44         }
45         return false;
46     }
47 };
View Code

想详细了解的可以去这里https://leetcode-cn.com/problems/permutation-in-string/solution/zi-fu-chuan-de-pai-lie-by-leetcode-solut-7k7u/

字符串的排列(双指针) 相关文章

  1. 剑指 Offer 58 - I. 翻转单词顺序 + 双指针

    剑指 Offer 58 - I. 翻转单词顺序 Offer_58_1 题目描述 方法一:使用Split函数 package com.walegarrett.offer;/** * @Author WaleGarrett * @Date 2021/2/12 17:38 */import java.util.Arrays;/** * 题目描述:输入一个英文句子,翻转句子中单词的顺序,但

  2. 剑指 Offer 57 - II. 和为s的连续正数序列 + 双指针 + 数论

    剑指 Offer 57 - II. 和为s的连续正数序列 Offer_57_2 题目描述 方法一:暴力枚举 package com.walegarrett.offer;/** * @Author WaleGarrett * @Date 2021/2/12 16:42 *//** * 题目描述:输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至

  3. C语言用指向指针的指针对5个字符串排序输出

    例81:C语言实现用指向指针的指针的方法对5个字符串排序并输出。 解题思路:读者看着道题的时候,首先要知道什么时指针,指向指针的指针应该怎么用,一般在开发中不这样用,读者要看明白,这个很锻炼思维的。 C语言源代码演示: #includestdio.h//头文件?#in

  4. Python 3的f-Strings:增强的字符串格式语法(指南)

    最近也在一个视频网站的爬虫,项目已经完成,中间有不少需要总结的经验。 从Python 3.6开始,f-Strings是格式化字符串的一种很棒的新方法。与其他格式化方式相比,它们不仅更具可读性,更简洁且不易出错,而且速度更快! Python中的“老式”字符串格式化 在P

  5. Leetcode 567. 字符串的排列(滑动窗口)

    给定两个字符串 **s1** 和 **s2**,写一个函数来判断 **s2** 是否包含 **s1** 的排列。换句话说,第一个字符串的排列之一是第二个字符串的子串。滑动窗口,s2包含s1的排列当且仅当s2存在一个子串,这个子串与s1对应字母个数相同。可以用大小为26的数组记录s1

  6. python中字符串连接的四种方式

    推荐 以下实例展示了join()的使用方法#!/usr/bin/pythonstr = "-";seq = ("a", "b", "c"); # 字符串序列print str.join( seq );以上实例输出结果如下:a-b-c 1、字符串之间连接 ‘aa’ ‘bb’ 可以中间为空格 或者什么都没有。 那么输出都是两者之间紧密相连

  7. Leetcode 567 字符串的排列

    题目定义: 给定两个字符串s1和s2,写一个函数来判断 s2 是否包含 s1的排列。换句话说,第一个字符串的排列之一是第二个字符串的子串。示例1:输入: s1 = "ab" s2 = "eidbaooo"输出: True解释: s2 包含 s1 的排列之一 ("ba"). 示例2:输入: s1= "ab" s2 = "eid

  8. C指针

    指针 1.指针基本介绍 指针是C语言的精华,也是C语言的难点 指针,就是内存的地址;所谓指针变量,也就是保存了内存地址的变量,关于指针的基本使用,在讲解变量的时候做了入门级的介绍 获取变量的地址,用,比如:int num=10,获取num的地址:num 指针类型,

  9. STL

    仅自用,感谢zzuacm 一.string(字符串) 例题 https://pintia.cn/problem-sets/994805046380707840/problems/11119145994086645 intmain(){stringstr;getline(cin,str);for(inti=0;istr.length();i++){if(str[i]=='6'){intj=1;//j代表连续6的个数while(i+js

  10. PAT 甲级 1006 Sign In and Sign Out 字符串

    地址https://pintia.cn/problem-sets/994805342720868352/problems/994805516654460928 题目大意是 按照HH:MM:SS 形式输入一个员工的签到签出时间,要求我们找到最早签到和最晚签出的员工id 输入格式 第一行 一个整数 N 表示有N个员工 下面N行的格式是ID_num

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词