LeetCode Permutation in String

原题链接在这里：https://leetcode.com/problems/permutation-in-string/description/

题目：

Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.

Example 1:

Input:s1 = "ab" s2 = "eidbaooo"

Output:True

Explanation: s2 contains one permutation of s1 ("ba").

Example 2:

Input:s1= "ab" s2 = "eidboaoo"

Output: False

Note:

The input strings only contain lower case letters.
The length of both given strings is in range [1, 10,000].

题解：

如何知道s1是s2某一段的permutation. 只要确定这一段的char count相等就行.

利用sliding window 长度为s1.length累计char count.

Note: check sum == 0 before moving walker. "ab", "bao", runner = 2, walker = 0, check sum == 0.

Time Complexity: O(n). n = s1.length()+s2.length().

Space: O(1).

AC Java:

 class Solution {

     public boolean checkInclusion(String s1, String s2) {

         if(s1 == null || s2 == null || s1.length() > s2.length()){

             return false;

         }

         int [] map = new int[256];

         for(int i = 0; i<s1.length(); i++){

             map[s1.charAt(i)]++;

         }

         int walker = 0;

         int runner = 0;

         int sum = s1.length();

         while(runner < s2.length()){

             if(map[s2.charAt(runner++)]-- > 0){

                 sum--;

             }

             if(sum == 0){

                 return true;

             }

             if(runner-walker==s1.length() && map[s2.charAt(walker++)]++ >= 0){

                 sum++;

             }

         }

         return false;

     }

 }

类似Find All Anagrams in a String.

巴特西

LeetCode Permutation in String

最新文章

热门文章