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
Constraints:
1 <= s1.length, s2.length <= 104s1 and s2 consist of lowercase English letters.class Solution {
public boolean checkInclusion(String s1, String s2) {
int n1 = s1.length(), n2 = s2.length();
char[] cs = s1.toCharArray();
Arrays.sort(cs);
String S1 = new String(cs);
for (int i = 0; i <= n2 - n1; i++) {
char[] sub = s2.substring(i, i + n1).toCharArray();
Arrays.sort(sub);
if(new String(sub).equals(S1))
return true;
// System.out.println(sub);
}
return false;
}
}class Solution {
public boolean checkInclusion(String s1, String s2) {
int[] freq = new int[26];
int n1 = s1.length(), n2 = s2.length();
if (n1 > n2)
return false;
for (char c : s1.toCharArray())
freq[c - 'a']++;
char[] cs = s2.toCharArray();
for (int i = 0; i < n1; i++)
freq[cs[i] - 'a']--; // enter sliding window
if (checkMatch(freq))
return true;
for (int i = n1; i < n2; i++) {
freq[cs[i - n1] - 'a']++; // exit sliding window
freq[cs[i] - 'a']--; // enter sliding window
if (checkMatch(freq))
return true;
}
return false;
}
private boolean checkMatch(int[] freq) {
// System.out.println(Arrays.toString(freq));
for (int i : freq)
if (i != 0)
return false;
return true;
}
}