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;
    }
}
打赏

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.