PattySung

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

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

<解題>


class Solution {
        public boolean checkInclusion(String s1, String s2) {
	    if(s1.length() > s2.length()) return false;
        
        int[] arr1 = new int[26]; 
        int[] arr2 = new int[26];
        
        for(int i = 0; i < s1.length(); i++){
            arr1[s1.charAt(i) - 'a']++; 
            arr2[s2.charAt(i) - 'a']++; 
        }
        
        if(Arrays.equals(arr1, arr2)) return true;
        
        int front = 0;
        int back = s1.length();
        while(back < s2.length()){
            arr2[s2.charAt(front) - 'a']--; //每次將窗口的前一個字符排除
            arr2[s2.charAt(back) - 'a']++;  //每次將窗口後一個字符加入
            
            if(Arrays.equals(arr1, arr2)) return true;
            front++;
            back++;
        }
        return false;
    }
}

Time: O(n) Space: O(1)

Leetcode-567. Permutation in String

<解題>