567. Permutation 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 
 1 class Solution {
 2     public boolean checkInclusion(String t, String s) {
 3         if (t.length() > s.length()) return false;
 4 
 5         Map<Character, Integer> map = new HashMap<>();
 6         for (int i = 0; i < t.length(); i++) {
 7             char ch = t.charAt(i);
 8             map.put(ch, map.getOrDefault(ch, 0) + 1);
 9         }
10         int begin = 0, end = 0;
11         int counter = t.length();
12         while (end < s.length()) {
13             char endChar = s.charAt(end);
14             if (map.containsKey(endChar)) {
15                 if (map.get(endChar) > 0) {
16                     counter--;
17                 }
18                 map.put(endChar, map.get(endChar) - 1);
19             }
20 
21             while (counter == 0) {
22                 if (end - begin + 1 == t.length()) {
23                     return true;
24                 }
25                 char beginChar = s.charAt(begin);
26                 if (map.containsKey(beginChar)) {
27                     map.put(beginChar, map.get(beginChar) + 1);
28                     if (map.get(beginChar) > 0) {
29                         counter++;
30                     }
31                 }
32                 begin++;
33             }
34             end++;
35         }
36         return false;
37     }
38 }

 this question is the same with 438. Find All Anagrams in a String

上一篇:有四个数字:1、2、3、4,能组成多少个互不相同且无重复数字的三位数?各是多少?


下一篇:CDR简单几步绘制漂亮的璀璨星光矢量图