首页 > 其他分享 >567. 字符串的排列

567. 字符串的排列

时间:2023-03-31 14:55:08浏览次数:52  
标签:排列 s2 s1 567 need window right 字符串 valid

力扣题目链接

给你两个字符串 s1 和 s2 ,写一个函数来判断 s2 是否包含 s1 的排列。如果是,返回 true ;否则,返回 false 。

换句话说,s1 的排列之一是 s2 的 子串 。

示例 1:

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

示例 2:

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

提示:

  • 1 <= s1.length, s2.length <= 104
  • s1 和 s2 仅包含小写字母
class Solution {
    public boolean checkInclusion(String s1, String s2) {
        HashMap<Character, Integer> window = new HashMap<>();
        HashMap<Character, Integer> need = new HashMap<>();
        for (char c : s1.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = 0;
        int valid = 0;
        while (right < s2.length()) {
            char c = s2.charAt(right);
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                //包装类需要使用equals判断是否相等
                if (window.get(c).equals(need.get(c)))
                    valid++;
            }

            //System.out.println("window: [" + left + "," + right + ")");

            if (right - left == s1.length()) {
                if (valid == need.size()) {
                    return true;
                }
                char d = s2.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    //只有先判断相等valid才能减1
                    if (window.get(d).equals(need.get(d)))
                        valid--;
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return false;
    }
}

 

标签:排列,s2,s1,567,need,window,right,字符串,valid
From: https://www.cnblogs.com/Co3y/p/17276281.html

相关文章

  • day8| 344.反转字符串;541.反转字符串II;剑指offer 05.替换空格;151.翻转字符串里的单词
    344.反转字符串 题目简述:编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组s的形式给出。不要给另外的数组分配额外的空间,你必须原地修改输入数组,使用O(1)的额外空间解决这一问题。 解题思路:没什么好说的,直接双指针 代码如下:classSolution:de......
  • 全网最详细中英文ChatGPT-GPT-4示例文档-智能编写Python注释文档字符串从0到1快速入门
    目录Introduce简介setting设置Prompt提示Sampleresponse回复样本APIrequest接口请求python接口请求示例node.js接口请求示例curl命令示例json格式示例其它资料下载ChatGPT是目前最先进的AI聊天机器人,它能够理解图片和文字,生成流畅和有趣的回答。如果你想跟上AI时代的潮流......
  • 简单介绍python列表元素拼接成字符串的4种方法
    本文主要介绍了python列表元素拼接成字符串的4种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧前言我们在分析列表数据时,常常需要对列表数据进行输出或多列表关联拼接。直接使用列表,列表中的各元素以逗......
  • 字符串常用方法
    1.capitalize()方法:将字符串的首字母大写。str="hello,world"print(str.capitalize())输出:Hello,world2.casefold()方法:将字符串转换为小写并删除所有大小写特有的字符,使字符串可以比较。str="Hello,WORLD"print(str.casefold())输出:hello,world3.center()方......
  • C#文档转为Base64位字符串
    publicstaticstringDocumentToBase64Str(stringfileName){FileStreamfilestream=newFileStream(fileName,FileMode.Open);byte[]bt=newbyte[filestream.Length];//调用read读取方法filestr......
  • day29 打卡491.递增子序列 46.全排列 47.全排列 II
    day29打卡491.递增子序列46.全排列47.全排列II491.递增子序列491题目链接classSolution{List<List<Integer>>result=newArrayList<>();LinkedList<......
  • 力扣---面试题 01.09. 字符串轮转
    字符串轮转。给定两个字符串s1和s2,请编写代码检查s2是否为s1旋转而成(比如,waterbottle是erbottlewat旋转后的字符串)。示例1:输入:s1="waterbottle",s2="erbottlewat"......
  • 代码随想录day 28 491. 递增子序列 | * 46.全排列 | 47.全排列 II
    给定一个整型数组,你的任务是找到所有该数组的递增子序列,递增子序列的长度至少是2。示例:输入:[4,6,7,7]输出:[[4,6],[4,7],[4,6,7],[4,6,7,7],[6,7......
  • 实验2 字符串和列表
    task1.pyx='nbaFIFA'print(x.upper())print(x.lower())print(x.swapcase())print()x='abc'print(x.center(10,'*'))print(x.ljust(10,'*'))print(x.rjust......
  • JavaScript系列 -> 字符串方法 replace 的第二个参数为函数
    本篇文章要介绍,当字符串的replace方法第二个参数为函数的使用。示例代码:functionfn(str){this.str=str;}fn.prototype.format=function(){vararg=......