Thursday, September 20, 2018

567. Permutation in String

567Permutation in String
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:
  1. The input strings only contain lower case letters.
  2. The length of both given strings is in range [1, 10,000].
--------------------
Sliding window

class Solution {
    public boolean checkInclusion(String s1, String s2) {
        Map<Character, Integer> map = getMap(s1);
        int count = s1.length();
        int start = -1;
        
        for (int i = 0; i < s2.length(); i++) {
            char c = s2.charAt(i);
            if (map.containsKey(c) && map.get(c) > 0) {
                if (count == s1.length()) start = i;

                map.put(c, map.get(c) - 1);
                count--;
                if (count == 0) return true;

            }else if ((map.containsKey(c) && map.get(c) == 0) || !map.containsKey(c)) {
                while (count < s1.length() && s2.charAt(start) != c) {
                    count++;
                    map.put(s2.charAt(start), map.get(s2.charAt(start)) + 1);
                    start++;
                }

                start++;
            }
        }
        
        return false;
    }
    
    private Map<Character, Integer> getMap(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        
        return map;
    }
    
}

No comments:

Post a Comment