Java
import java.util.Arrays;
/*
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].
*/
public class Permutation_in_String {
public static void main(String[] args) {
Permutation_in_String out = new Permutation_in_String();
Solution s = out.new Solution();
System.out.println(s.checkInclusion("ab", "eidbaooo"));
System.out.println(s.checkInclusion("ab", "eidboaoo"));
}
public class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}
int window = s1.length();
// N * N
for(int i = 0; i + window - 1 < s2.length(); i++) {
if (isPerm(s1, s2.substring(i, i + window))) {
return true;
}
}
return false;
}
// better permutation check: o(N)
public boolean isPerm(String s1, String s2) {
if(s1.length() != s2.length()) {
return false;
}
int[] count = new int[256];
// each char of s1: +1
// each char of s2: -1
// final check: permutation if all 0s array
for(int i = 0; i < s1.length(); i++) {
char s1char = s1.charAt(i);
count[s1char] = count[s1char] + 1;
char s2char = s2.charAt(i);
count[s2char] = count[s2char] - 1;
}
for(int each: count) {
if (each != 0) {
return false;
}
}
return true;
}
}
// Time Limit Exceeded
public class Solution2 {
public boolean checkInclusion(String s1, String s2) {
if (s1.length() > s2.length()) {
return false;
}
int window = s1.length();
// N * NlogN
for(int i = 0; i + window - 1 < s2.length(); i++) {
if (isPerm(s1, s2.substring(i, i + window))) {
return true;
}
}
return false;
}
// NlogN
public boolean isPerm(String s1, String s2) {
if(s1.length() != s2.length()) {
return false;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
Arrays.sort(c1); // NlogN
Arrays.sort(c2);
for(int i = 0; i < c1.length; i++) {
if(c1[i] != c2[i]) {
return false;
}
}
return true;
}
}
}
Java
class Solution {
public boolean checkInclusion(String s1, String s2) {
if (s1 == null || s2 == null || s1.length() > s2.length())
return false;
if (s2.indexOf(s1) >= 0)
return true;
int[] counts1 = new int[26];
int[] counts2 = new int[26];
int length1 = s1.length(), length2 = s2.length();
for (int i = 0; i < length1; i++) {
char c1 = s1.charAt(i);
counts1[c1 - 'a']++;
char c2 = s2.charAt(i);
counts2[c2 - 'a']++;
}
if (checkSubstring(counts1, counts2))
return true;
for (int i = length1; i < length2; i++) {
char prevC = s2.charAt(i - length1), curC = s2.charAt(i);
counts2[prevC - 'a']--;
counts2[curC - 'a']++;
if (checkSubstring(counts1, counts2))
return true;
}
return false;
}
public boolean checkSubstring(int[] counts1, int[] counts2) {
for (int i = 0; i < 26; i++) {
if (counts1[i] != counts2[i])
return false;
}
return true;
}
}