Permutation in String

Problem:
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
Analysis:
Find All Anagarms in a String的马甲题,简化版。。。
Solution:

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()) {
            return false;
        }
        int[] map = new int[256];
        for (char c: s1.toCharArray()) {
            map[c]++;
        }
        int l = 0, r = 0, counter = s1.length();
        while (r < s2.length()) {
            if (map[s2.charAt(r++)]--> 0) counter--;
            if (counter == 0) return true;
            if (r - l == s1.length() && map[s2.charAt(l++)]++ >= 0) counter++;
        }
        return false;

    }
}

评论

此博客中的热门博文

663. Equal Tree Partition

776. Split BST

426. Convert Binary Search Tree to Sored Doubly Linked List