Simple DP Python beats 90%, O(n) time, O(1) space


  • 0

    Using a dictionary to store the highest value for each character from a to z, and we can handle the duplicate characters in p easily.

    class Solution(object):
        def findSubstringInWraproundString(self, p):
            """
            :type p: str
            :rtype: int
            """
            values = collections.defaultdict(int)
            last_c, last_v = "", 0
            for c in p:
                v = last_v + 1 if last_c and (ord(c) - ord(last_c)) % 26 == 1 else 1
                values[c] = max(values[c], v)
                last_c, last_v = c, v
            return sum(values.values())
    

    Evolved from 1 dimensional DP version as attached.

    class Solution(object):
        def findSubstringInWraproundString(self, p):
            """
            :type p: str
            :rtype: int
            """
            mark = collections.defaultdict(int)
            n = len(p)
            dp = [0] * n
            for i in range(n):
                dp[i] = dp[i-1]+1 if i and (ord(p[i]) - ord(p[i-1])) % 26 == 1 else 1
                mark[p[i]] = max(mark[p[i]], dp[i])
            return sum(mark.values())
    

  • 0
    P

    Can skip the else part if dp is initialized as [1]*n.


Log in to reply
 

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