Python Solution

  • 1

    This solution might look a bit verbose but it is straight forward. dp[i] is the number of qualified substrings ending at the position i in p, seen is a dictionary keyed by the character c that maintains the greatest number of qualified substrings ending at the char c.

    class Solution(object):
        def findSubstringInWraproundString(self, p):
            :type p: str
            :rtype: int
            N = len(p)
            if N <= 1: return N
            dp = [0 for i in range(N)]
            start, seen = 0, {}
            dp[0], seen[p[0]] = 1, 1
            for i in range(1, N):
                if p[i - 1] == 'z' and p[i] == 'a' or ord(p[i - 1]) + 1 == ord(p[i]):
                    x = i - start + 1
                    if p[i] not in seen:
                        dp[i] = x
                        seen[p[i]] = dp[i]
                        if x > seen[p[i]]:
                            dp[i] = x - seen[p[i]]
                            seen[p[i]] = x
                            dp[i] = 0
                    if p[i] not in seen:
                        dp[i] = 1
                        seen[p[i]] = dp[i]
                        dp[i] = 0
                    start = i
            return sum(dp)

  • 0

    Thank you. Not verbose at all. Most of the time, from a reader's point of view, especially from someone who struggles to solve the problem, a solution's clearness tops conciseness. Hands down! If you had posted a solution that was more difficult to understand than to solve the problem itself, you did not post a helpful solution. So, don't worry about it being verbose. After all, your intention is to help us understand; and once we do, we can spin it ourselves however we want. See, I spun it and made it less verbose but harder to understand. So, thank you again for sharing your easy-to-understand code.

    def findSubstringInWraproundString(self, p):
        if not p: return 0
        basePattern = 'z' + string.ascii_lowercase
        visited = collections.defaultdict(int)
        subStrLen, visited[p[0]] = 1, 1
        for i in range(1, len(p)):
            subStrLen = subStrLen+1 if p[i-1:i+1] in basePattern else 1
            visited[p[i]] = max(subStrLen, visited[p[i]]) if p[i] in visited else subStrLen
        return sum(visited.values())

Log in to reply

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