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; } } }
-
// OJ: https://leetcode.com/problems/permutation-in-string/ // Time: O(B) // Space: O(1) class Solution { public: bool checkInclusion(string a, string b) { if (a.size() > b.size()) return false; int N = a.size(), cnts[26] = {}; for (char c : a) cnts[c - 'a']++; for (int i = 0; i < b.size(); ++i) { cnts[b[i] - 'a']--; if (i - N >= 0) cnts[b[i - N] - 'a']++; bool match = true; for (int j = 0; j < 26 && match; ++j) { if (cnts[j]) match = false; } if (match) return true; } return false; } };
-
class Solution(object): def checkInclusion(self, s1, s2): """ :type s1: str :type s2: str :rtype: bool """ d = {} n = len(s1) for c in s1: d[c] = d.get(c, 0) + 1 window = {} for i, c in enumerate(s2): window[c] = window.get(c, 0) + 1 if i >= len(s1): window[s2[i - n]] = window.get(s2[i - n], 0) - 1 if window[s2[i - n]] == 0: del window[s2[i - n]] if window == d: return True return False
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; } }
-
// OJ: https://leetcode.com/problems/permutation-in-string/ // Time: O(B) // Space: O(1) class Solution { public: bool checkInclusion(string a, string b) { if (a.size() > b.size()) return false; int N = a.size(), cnts[26] = {}; for (char c : a) cnts[c - 'a']++; for (int i = 0; i < b.size(); ++i) { cnts[b[i] - 'a']--; if (i - N >= 0) cnts[b[i - N] - 'a']++; bool match = true; for (int j = 0; j < 26 && match; ++j) { if (cnts[j]) match = false; } if (match) return true; } return false; } };
-
class Solution(object): def checkInclusion(self, s1, s2): """ :type s1: str :type s2: str :rtype: bool """ d = {} n = len(s1) for c in s1: d[c] = d.get(c, 0) + 1 window = {} for i, c in enumerate(s2): window[c] = window.get(c, 0) + 1 if i >= len(s1): window[s2[i - n]] = window.get(s2[i - n], 0) - 1 if window[s2[i - n]] == 0: del window[s2[i - n]] if window == d: return True return False