Search
 
SCRIPT & CODE EXAMPLE
 
CODE EXAMPLE FOR PYTHON

permutation in a string

import collections
class Solution:
    def checkInclusion(self, s1, s2):
        """
        :type s1: str
        :type s2: str
        :rtype: bool
        """
        '''
        Apprach 3:
        Just changing the collections.Counter to collections.defaultdict
        improved the speed
        94.36%, Nice. :)
        
        '''
        ctr1 = collections.defaultdict(int)
        ctr2 = collections.defaultdict(int)
        for x in s1: ctr1[x] += 1
        for x in s2[:len(s1)]: ctr2[x] += 1
            
        i = 0; j = len(s1)
        
        while j < len(s2):
            if ctr2 == ctr1: return True
            ctr2[s2[i]] -= 1
            if ctr2[s2[i]] < 1: ctr2.pop(s2[i]); 
            ctr2[s2[j]] = ctr2.get(s2[j], 0) + 1
            i += 1; j += 1
            
        return ctr2 == ctr1
        
        '''
        Approach 2:
        Use the same counter but much more effeciently
        63% beated, okay not bad..
        two pointers i(front) j(last), delete and add accordingly and check for the counts
        
        # Code Below
        '''
        ctr1 = collections.Counter(s1)
        ctr2 = collections.Counter(s2[:len(s1)])
            
        i = 0; j = len(s1)
        
        while j < len(s2):
            if ctr2 == ctr1: return True
            ctr2[s2[i]] -= 1
            if ctr2[s2[i]] < 1: ctr2.pop(s2[i]); 
            ctr2[s2[j]] = ctr2.get(s2[j], 0) + 1
            i += 1; j += 1
            
        return ctr2 == ctr1
    
        
        '''
        1. Approach 1
        Things i Missed: 
            - Had the len(s2) - len(s1) + 1: forgot to add the 1 in the if condition 
        Ultra easy solution
        Slice and check for the equality
        5% beat, yuck !! 
        # Code below
       '''
        ctr1 = collections.Counter(s1)
        i = 0
        while i < len(s2) - len(s1) + 1:
            if s2[i] in ctr1:
                ctr2 = collections.Counter(s2[i: i+len(s1)])
                if ctr1 == ctr2: return True
            i += 1
        return False

        
Source by leetcode.com #
 
PREVIOUS NEXT
Tagged: #permutation #string
ADD COMMENT
Topic
Name
7+6 =