Python O(n) DP


  • 5

    I use cmap[c] to store the maximum length of sub-string starts with c.

    The time complexity of the code below is O(n) as well.

    class Solution(object):
        def findSubstringInWraproundString(self, p):
            """
            :type p: str
            :rtype: int
            """
            pattern = 'zabcdefghijklmnopqrstuvwxyz'
            cmap = collections.defaultdict(int)
            start = end = 0
            for c in range(len(p)):
                if c and p[c-1:c+1] not in pattern:
                    for x in range(start, end):
                        cmap[p[x]] = max(end - x, cmap[p[x]])
                    start = c
                end = c + 1
            for x in range(start, end):
                cmap[p[x]] = max(end - x, cmap[p[x]])
            return sum(cmap.values())
    

Log in to reply
 

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