leetcode 567. 字符串的排列(滑动窗口-java)

这篇具有很好参考价值的文章主要介绍了leetcode 567. 字符串的排列(滑动窗口-java)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

字符串的排列

难度 -中等
leetcode567. 字符串的排列

给你两个字符串 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 <= 1e4
s1 和 s2 仅包含小写字母
leetcode 567. 字符串的排列(滑动窗口-java),java,算法,数据结构,leetcode,java,python,算法,数据结构

滑动窗口

这种题目,是明显的滑动窗口算法,相当给你一个 S 和一个 T,请问你 S 中是否存在一个子串,包含 T 中所有字符且不包含其他字符。
题目要求 t 的排列之一是 s 的一个子串。而子串必须是连续的,所以要求的 s 子串的长度跟 t 长度必须相等。
那么我们有必要把 t 的每个排列都求出来吗?当然不用。如果字符串 a 是 b 的一个排列,那么当且仅当它们两者中的每个字符的个数都必须完全相等。
所以,根据上面两点分析,我们已经能确定这个题目可以使用 滑动窗口 + hash表 来解决。

我们使用一个长度和 t 长度相等的固定窗口大小的滑动窗口,在 s 上面从左向右滑动,判断 s 在滑动窗口内的每个字符出现的个数是否跟 t 每个字符出现次数完全相等。

我们定义 need是对 t 内字符出现的个数的统计,定义 wind是对 s 内字符出现的个数的统计。在窗口每次右移的时候,需要把右边新加入窗口的字符个数在 wind 中加 1,把左边移出窗口的字符的个数减 1。如果 need== wind,那么说明窗口内的子串是 t 的一个排列,返回 True;如果窗口已经把 s遍历完了仍然没有找到满足条件的排列,返回 False。

代码演示

 public boolean checkInclusion(String t, String s) {
        int n = t.length(), m = s.length();
        if (n > m) {
            return false;
        }
        HashMap<Character, Integer> need = new HashMap<>();
        HashMap<Character, Integer> wind = new HashMap<>();
        for (char c : t.toCharArray()){
            need.put(c,need.getOrDefault(c,0) + 1);
        }
        int left = 0;
        int right  = 0;
        int valid = 0;
        while (right < m){
            //右指针 向右移动 窗口扩大
            char c = s.charAt(right);
            right++;
            //判断新进来的字符 是否是需要的。
            if (need.containsKey(c)){
                wind.put(c,wind.getOrDefault(c,0) + 1);
                if (wind.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            //判断是否需要缩小窗口。
            while (right - left >= n){
                //找到直接返回true
                if (valid == need.size()){
                    return true;
                }
                //如何缩小窗口
                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)){
                    if (need.get(d).equals(wind.get(d))){
                        valid--;
                    }
                    wind.put(d,wind.get(d) - 1);
                }
            }
        }
        return false;
    }

进阶优化版

这道题目中说明只有小写字母,因此我们可以用数组代替hash表,进行优化,数组代替hash表有两个好处,
1.优化了常数时间,数组的时间效率高于hash表,
2.优化了内存,数组更省空间,

代码演示:

  public boolean checkInclusion(String t, String s) {
        int n = t.length(), m = s.length();
        if (n > m) {
            return false;
        }
        int[] need = new int[26];
        int[] wind = new int[26];
        for (char c : t.toCharArray()){
           ++need[c - 'a'];
        }
        int left = 0;
        int right  = 0;
        while (right < m){
            //右指针 向右移动 窗口扩大
            char c = s.charAt(right);
            right++;
            //判断新进来的字符 是否是需要的。
            if (need[c - 'a'] != 0){
                ++wind[c - 'a'];
            }
            //判断是否需要缩小窗口。
            while (right - left >= n){
                //找到直接返回true
                if (Arrays.equals(wind,need)){
                    return true;
                }
                //如何缩小窗口
                char d = s.charAt(left);
                left++;
                if (need[d - 'a'] != 0){
                    --wind[d - 'a'];
                }
            }
        }
        return false;
    }

上期经典

leetcode76. 最小覆盖子串文章来源地址https://www.toymoban.com/news/detail-683485.html

到了这里,关于leetcode 567. 字符串的排列(滑动窗口-java)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • rust踩雷笔记(2)——一道hard带来的思考[哈希表、字符串、滑动窗口]

    今天被一道hard恶心坏了,算法不难,用C++几分钟的事。用rust主要还是缺乏对语言的熟练度,记录一下,主要的坑在下面这个操作: 对String取其中某个位置的char。 可能你会有疑问:这不是直接nth()取就行了么。没错,我看有些题解也是这样做的,但是那样会在某些字符长度很

    2024年02月12日
    浏览(36)
  • 力扣hot100 找到字符串中所有字母异位词 滑动窗口 双指针 一题双解

    Problem: 438. 找到字符串中所有字母异位词 👩‍🏫 参考题解 ⏰ 时间复杂度: O ( n ) O(n) O ( n ) 🌎 空间复杂度: O ( 1 ) O(1) O ( 1 ) ⏰ 时间复杂度: O ( n ) O(n) O ( n ) 🌎 空间复杂度: O ( 1 ) O(1) O ( 1 )

    2024年01月24日
    浏览(49)
  • 每日OJ题_算法_滑动窗口⑥_力扣438. 找到字符串中所有字母异位词

    目录 力扣438. 找到字符串中所有字母异位词 解析及代码1 解析及代码2 438. 找到字符串中所有字母异位词 - 力扣(LeetCode) 难度 中等 给定两个字符串  s  和  p ,找到  s   中所有  p   的  异位词  的子串,返回这些子串的起始索引。不考虑答案输出的顺序。 异位词  指由

    2024年01月24日
    浏览(48)
  • 递归--打印一个字符串的全部排列(java)

    自负串全排序: 举例: abc 的全排序是: abc acb bac bca cba cab 因为每个字符都要选,其实就是选择每个字符的顺序,那我们递归时,就可以把不同顺序一直递归下去. 代码演示 解题思路: 我们可以按上面的代码去做,只需要用HashSet 去保存答案,就会去重了,但这样并没有优化效率,在递归时

    2024年02月06日
    浏览(53)
  • 代码随想录复习 1047. 删除字符串中的所有相邻重复项 150 逆波兰表达式求值 239 滑动窗口最大值

    1047. 删除字符串中的所有相邻重复项 代码如下  func removeDuplicates(s string) string {             var  stack []byte   //结果栈数组             for i := 0 ; i  len(s) ; i++ {                 if len(stack)  0  stack[len(stack)-1] == s[i] {  //如果当前遍历到的元素

    2024年02月05日
    浏览(71)
  • LeetCode 1641. 统计字典序元音字符串的数目 / 1637. 两点之间不包含任何点的最宽垂直区域 / 1053. 交换一次的先前排列

    2023.3.29 每日一题 给你一个整数 n,请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。 字符串 s 按 字典序排列 需要满足:对于所有有效的 i,s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。 示例 1: 输入:n = 1 输出:5 解释:仅由元音组成

    2023年04月09日
    浏览(41)
  • 获取字符串的全排列(去除字符串中2个字符相同时造成的重复)

    一、概念 现有一个字符串,要打印出该字符串中字符的全排列。 以字符串abc为例,输出的结果为:abc、acb、bac、bca、cab、cba。 以字符串aab为例,输出的结果为:aab、aba、baa。 二、代码 致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分

    2024年04月16日
    浏览(40)
  • 【字符串 简单】LeetCode 14. 最长公共前缀 Java

    我的思路: 给字符串数组按照字符串的长度从长到短排序,因为最长公共前缀最长的话,也只能是字符串数组中最短的那一个字符串 设置一个index变量,表示当前正在检查字符数组中所有字符串的index位置 循环遍历字符串数组n遍,n也就是最长公共前缀的长度 其他思路,方法

    2024年02月15日
    浏览(40)
  • Java【手撕滑动窗口】LeetCode 3. “无重复字符的最长子串“, 图文详解思路分析 + 代码

    各位读者好, 我是小陈, 这是我的个人主页, 希望我的专栏能够帮助到你: 📕 JavaSE基础: 基础语法, 类和对象, 封装继承多态, 接口, 综合小练习图书管理系统等 📗 Java数据结构: 顺序表, 链表, 堆, 二叉树, 二叉搜索树, 哈希表等 📘 JavaEE初阶: 多线程, 网络编程, TCP/IP协议, HTTP协议

    2024年02月11日
    浏览(40)
  • 31 对集合中的字符串,按照长度降序排列

            思路:使用集合的sort方法,新建一个Comparator接口,泛型是String,重写里面的compare方法。         运行结果:          扩充:点击Comparator,查看接口内部:发现加了@FunctionalInterface,说明可以使用箭头函数,直接使用箭头函数就能表示Comparator接口以及它的compara

    2024年02月14日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包