leetcode 467 Unique Substrings in Wraparound String
z
 2019-06-11 11:07:52  

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 pare 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:

1
2
3
4
Input: "a"
Output: 1

Explanation: Only the substring "a" of string "a" is in the string s.

Example 2:

1
2
3
Input: "cac"
Output: 2
Explanation: There are two substrings "a", "c" of string "cac" in the string s.

Example 3:

1
2
3
Input: "zab"
Output: 6
Explanation: There are six substrings "z", "a", "b", "za", "ab", "zab" of string "zab" in the string s.

  • 判断是否是连续的字符: (ord(i) - ord(i-1)) % 26 == 1

  • 有可能有重复的substring。比如，如果出现 abc和abcd的话，我们只需要计入abcd产生的substring

  • 对于每遇到的一个字符，确定以该字符结尾连续substring有多少个即可。比如，对于abcd，

    • a结尾：1
    • b结尾：2
    • c结尾：3
    • d结尾：4
    • 总共：1+2+3+4 = 10，即为所求的abcd产生的有序的子串的个数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    class Solution(object):
        def findSubstringInWraproundString(self, p):
            """
            :type p: str
            :rtype: int
            """
            dic = {i:1 for i in p}
            l = 1
            for i, j in zip(p, p[1:]): # 遍历判断前后两者的关系的时候，可以用这种方式
                if (ord(j) - ord(i)) % 26 == 1:
                    l += 1
                else:
                    l = 1
                dic[j] = max(dic[j], l) # 只保存以j结尾产生的最长的串
            return sum(dic.values())