【leetcode】467. Unique Substrings in Wraparound String

逃离我推掉我的手 2022-01-10 06:11 135阅读 0赞

**题目如下：**

> Consider the string `s` to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so `s` will look like this: "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
> 
> Now we have another string `p`. Your job is to find out how many unique non-empty substrings of `p` are present in `s`. In particular, your input is the string `p` and you need to output the number of different non-empty substrings of `p` in the string `s`.
> 
> Note: `p` consists of only lowercase English letters and the size of p might be over 10000.
> 
> Example 1:
> 
>     Input: "a"
>     Output: 1
>     
>     Explanation: Only the substring "a" of string "a" is in the string s.
> 
>  
> 
> Example 2:
> 
>     Input: "cac"
>     Output: 2
>     Explanation: There are two substrings "a", "c" of string "cac" in the string s.
> 
>  
> 
> Example 3:
> 
>     Input: "zab"
>     Output: 6
>     Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

**解题思路：**本题的关键在于求出以每个字符的开头的最长连续字符子串的长度。例如input为"zabza"，"z"开头的连续子串是"zab"和"za"，如果要求以"z"开头的所有子串，那么"zab"的结果肯定是包含"za"的，所以这也就是为什么要求出以每个字符的开头的最长连续字符子串的长度。"zab"中以"z"开头的所有子串的个数就等于这个字符串的长度("z","za","zab")，所以本题的答案只要求出出现的所有不同的字符开头的最长连续字符子串的长度的总和即可。

**代码如下：**

class Solution(object):
        def findSubstringInWraproundString(self, p):
            """
            :type p: str
            :rtype: int
            """
            p += '#'  # add a end character
            nextDic = {}
            dic = {}
            letter = "abcdefghijklmnopqrstuvwxyz"
            for i in range(len(letter)-1):
                nextDic[letter[i]] =letter[i+1]
            nextDic['z'] = 'a'
            nextDic['#'] = 'END'
            res = 0
            lastChar = None
            count = 0
            for i in range(len(p)):
                if lastChar == None:
                    count += 1
                elif nextDic[lastChar] == p[i]:
                    count += 1
                else:
                    for inx in range(i-count,i):
                        length = i - inx
                        if p[inx] in dic:
                            dic[p[inx]] = max(dic[p[inx]],length)
                        else:
                            dic[p[inx]] = length
                    count = 1
                lastChar = p[i]
            for val in dic.itervalues():
                res += val
            return res

转载于:https://www.cnblogs.com/seyjs/p/10575226.html