LeetCode-567:字符串的排列

举报
小小谢先生 发表于 2022/04/16 02:13:10 2022/04/16
【摘要】 题目描述: 给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。 换句话说,第一个字符串的排列之一是第二个字符串的子串。 示例1: 输入: s1 = "ab" s2 = "eidbaooo" 输出: True 解释: s2 包含 s1 的排列之一 ("ba")....

题目描述:

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

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

示例1:

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

示例2:

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

 

思路分析:

看到子串就想到滑动窗口,先试着用滑动窗口解题。

直接套用labuladong的算法小抄的滑动窗口模板:


      class Solution {
         public boolean checkInclusion(String s1, String s2) {
             int len=s2.length();
              HashMap<Character,Integer> need=new HashMap<>();
              HashMap<Character,Integer> window=new HashMap<>();
             for(char c: s1.toCharArray()){
                  need.put(c,need.getOrDefault(c,0)+1);
              }
             int left=0,right=0,res=0;
             int valid=0;
             while(right<len){
                 char r=s2.charAt(right);
                  right++;
                 if(need.containsKey(r)){
                      window.put(r,window.getOrDefault(r,0) + 1);
                     if(need.get(r).equals(window.get(r))){
                          valid++;
                      }
                  }
                 while(right-left>=s1.length()){
                     if(valid==need.size()){
                         return true;
                      }
                     char l=s2.charAt(left);
                      left++;
                     if(need.containsKey(l)){
                         if(window.get(l).equals(need.get(l))){
                              valid--;
                          }
                          window.put(l,window.getOrDefault(l,0)-1);
                      }
                  }
              }
             return false;
          }
      }
  
 

 

文章来源: blog.csdn.net,作者:小小谢先生,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/xiewenrui1996/article/details/113786201

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。