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].
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