Skip to content

467 Unique Substrings in Wraparound String

467. Unique Substrings in Wraparound String

题目: https://leetcode.com/problems/Unique-Substrings-in-Wraparound-String/

难度:

Medium

思路:

有个无限长的字符串s,是由无数个「abcdefghijklmnopqrstuvwxyz」组成的。现在给你一个字符串p,求多少个p的非空子串在s中出现了?   

先考虑s的特性,满足条件(在s中)的p的子串只可能是abcd……z的连续序列(z后面是a), 我们只需要处理p中连续的部分就可以了。但是 举个例子,h-k的序列出现了,a-z的序列也出现了,那么只需要计算a-z的子串个数就可以了,因为h-k已经包含在a-z里了。考虑所有包含的情况,似乎就变得复杂了,a-z还可能被包含在x-za-z中,甚至更长的序列中。

但是如果考虑以某个字母结尾的子串个数,那么p中以该字母结尾的连续序列长度,就是满足条件的子串个数。如果以字母x结尾的连续序列有多个, 我们只需要最长的一个即可,因为其他短的序列都已经被长的包含进去了,例如'bcd'和'abcd',有了'abcd'就知道以d结尾的子串有4个,分别是‘d’,'cd','bcd','abcd',‘bcd’已经被包含进去了。最后求和,问题就解决了。 这样思考就非常简单了,代码也可以很容易写出来。

class Solution(object):
    def findSubstringInWraproundString(self, p):
        """
        :type p: str
        :rtype: int
        """
        letters = [0] * 26          #开始默认每个都是0
        length = 0
        for i in range(len(p)):
            curr = ord(p[i]) - ord('a')
            if i > 0 and ord(p[i-1]) != (curr-1)%26 + ord('a'):   #一旦开始不相等了就要将length重置为0
                length = 0
            length += 1                        #否则就说明继续与前面一个字符是连续的,length要加1才行
            if length > letters[curr]:     #length一直加,如果到i这个字符length比它的目前的最大连续子串长度还要长,那么肯定要更新letters
                letters[curr] = length
        return sum(letters)


回到顶部