LeetCode-567：字符串的排列

题目描述：

给定两个字符串 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