Share my python solution, detailed thought (while not elegant)


  • 0
    K
    class Solution(object):
        def getMaxRepetitions(self, s1, n1, s2, n2):
            """
            :type s1: str
            :type n1: int
            :type s2: str
            :type n2: int
            :rtype: int
            """
            # First, try to find s2 inside s1
            
            L1 = len(s1)
            L2 = len(s2)
            i = 0
            j = 0
            count = 0
            while i < L1:
                
                if s1[i] == s2[j]:
                    j += 1
                    if j == L2:
                        count += 1
                        j = 0
                
                i += 1
                
            # cannot find any single character of s2
            if count == 0 and j == 0:
                return 0
                
            # s1 contains at least one s2
            # concat two s1, we may find one more s2
            if count > 0:
                tmp = count
                i = 0
                while i < L1:
                    if s1[i] == s2[j]:
                        j += 1
                        if j == L2:
                            count += 1
                            j = 0
                
                    i += 1
            
    	    # no more s2 after concat
                if tmp * 2 == count:
                    return tmp * n1 / n2
                # we do have one more s2 after concat
                else:
                    return (tmp * n1 + n1 - 1) / n2 if n1 > 0 else 0
                    
            # Here count == 0, j != 0, means only part of s2 is found inside s1, in other words, we got a "dirty tail"
            # concat more s1 until we find a complete s2, and keep finding new s2, until the "dirty tail" is gone or remains the same, which means we finally find the pattern
            
            tmp = -1
            accArr = []
            acc = 1
            while j != 0 and j != tmp:
                tmp = j
     
                s1Num = 0
                findS2 = False
                while not findS2:
                    s1Num += 1
                    i = 0
                    hit = False
                    while i < L1:
                        if s1[i] == s2[j]:
                            hit = True
                            j += 1
                            if j == L2:
                                findS2 = True
                                count += 1
                                j = 0
                    
                        i += 1
                        
                    if not hit: # cannot find necessary characters
                        return 0
                        
                accArr.append(acc + s1Num) # accArr[i] = how many s1 are checked when we find i th complete s2
                acc += s1Num
                if acc > n1:
                    return (count - 1) / n2
                
            # pattern found!
        
            if j == 0:
                # (acc) number of s1 = (count) number of s2
                S = n1 / acc * count
                r = n1 % acc
    
                for num in accArr:
                    if num <= r:
                        S += 1
                    else:
                        break
    
                return S / n2
                
            if j == tmp:
                # (acc) number of s1 = (count) number of s2,now every new (s1Num) number of s1, gives us a new s2
                return ( (n1 - acc) / s1Num + count) / n2
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.