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
    
    

All Problems

All Solutions