题目描述：

LeetCode 467. Unique Substrings in Wraparound String

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.

题目大意：

字符串s是小写字母"abcdefghijklmnopqrstuvwxyz"的无限循环，s看起来像这样："...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."

现在我们有另外一个字符串p。你需要寻找p有多少个非空子串在s中出现。输入p，你需要输出s中有多少个不同的p的非空子串。

解题思路：

按照子串的首字母分类计数

用字典cmap记录以某字母开始的子串的最大长度

遍历字符串p，维护区间[start, end]，p[start ... end]是无限循环字符串s的一部分

更新p[start], p[start + 1], ... p[end]在cmap中的长度值

最终结果为cmap中value的和

Python代码：

class Solution(object):
    def findSubstringInWraproundString(self, p):
        """
        :type p: str
        :rtype: int
        """
        pattern = 'zabcdefghijklmnopqrstuvwxyz'
        cmap = collections.defaultdict(int)
        start = end = 0
        for c in range(len(p)):
            if c and p[c-1:c+1] not in pattern:
                for x in range(start, end):
                    cmap[p[x]] = max(end - x, cmap[p[x]])
                start = c
            end = c + 1
        for x in range(start, end):
            cmap[p[x]] = max(end - x, cmap[p[x]])
        return sum(cmap.values())

将上述代码中cmap的含义变更为记录以某字母结尾的子串的最大长度，可以使代码简化。

Python代码：

class Solution(object):
    def findSubstringInWraproundString(self, p):
        """
        :type p: str
        :rtype: int
        """
        pattern = 'zabcdefghijklmnopqrstuvwxyz'
        cmap = collections.defaultdict(int)
        clen = 0
        for c in range(len(p)):
            if c and p[c-1:c+1] not in pattern:
                clen = 1
            else:
                clen += 1
            cmap[p[c]] = max(clen, cmap[p[c]])
        return sum(cmap.values())

 

本文链接：http://bookshadow.com/weblog/2016/12/04/leetcode-unique-substrings-in-wraparound-string/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码