Leetcode 467. Unique Substrings in Wraparound String

题目链接：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.

　　大概翻译下题意，有个无限长的字符串s，是由无数个「abcdefghijklmnopqrstuvwxy」组成的。现在给你一个字符串p，求多少个p的非重复子串在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结尾的连续序列有多个， 我们只需要最长的一个即可，因为其他短的序列都已经被长的包含进去了。最后求和，问题就解决了。 这样思考就非常简单了，代码也可以很容易写出来。
　　以下是java代码，个人觉得看代码比看文字题解要更容易理解，关键是理解结尾字符的意义。

public class Solution {
public int findSubstringInWraproundString(String p) {
    int plen = p.length();
    int ans = 0;
    int curlen = 0;
    int[] subsum = new int[26];
    for (int i = 0; i < plen; i++) {
        if (i > 0 && (p.charAt(i)-p.charAt(i-1) == 1 || p.charAt(i)-p.charAt(i-1) == -25)) {
            curlen += 1;
        }
        else {
            curlen = 1;
        }
        int cur = p.charAt(i) - 'a';
        subsum[cur] = Math.max(subsum[cur], curlen);
    }
    for (int i = 0; i < 26; i++) {
        ans += subsum[i];
    }
    return ans;
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

文章来源: xindoo.blog.csdn.net，作者：xindoo，版权归原作者所有，如需转载，请联系作者。

原文链接：xindoo.blog.csdn.net/article/details/53560416