concise python solution for the repeat cycle detection idea


  • -1
    X

    just copied the idea from @70664914

    class Solution(object):
        def getMaxRepetitions(self, s1, n1, s2, n2):
            txt, tcycs, pat, pcycs = s1, n1, s2, n2
            psz = len(pat)
            tc2pi, pi2tc = [], {}
            pi = 0
            for tc in range(tcycs):
                tc2pi.append(pi)
                _tc = pi2tc.setdefault(pi%psz, tc)
                if _tc != tc:
                    break
                for c in txt:
                    if c == pat[pi%psz]:
                        pi += 1            
            else:
                return pi //psz //pcycs
            rep, remtcycs = divmod(tcycs - _tc, tc - _tc)
            return ( rep * (tc2pi[tc] - tc2pi[_tc]) + tc2pi[ _tc + remtcycs ] ) //psz //pcycs
    

Log in to reply
 

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