[LC 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.

一道简单的DP,code也不长,但关键是想明白是用DP做的。

从一个例子开始:”wyzas”。开始发现,这段string可以分成三段连续的substring,”w”, “yza”, “s”, 首尾只有一个substring,中间有3+2+1 = 6个,”y”, “z”, “a”, “yz”, “za”, “yza”。那么是不是找到所有这样的分段,加在一起就是答案呢?不是。因为还有重合的情况,例如 “xyzyz”, 两端连续的分别是”xyz”, “yz”,第二段是第一段的substring,所以并不能为总和贡献新的unique substring。此时又陷入了沉思-____-

解决问题关键的点是:unique substring的总和,即答案,是以字母’a’ – ‘z’结尾的max substring的和。例如在”yza”中:
以”y”结尾的max substring长度是1,对应找到的unique substring是”y”;
以”z”结尾的max substring长度是2,对应找到的unique substring是”z”和”yz”
以”a”结尾的max substring长度是3,对应找到的unique substring是”a”, “za”, 和”yza”
在第二个例子”xyzyz”中:
以”x”结尾的max substring长度是1,对应找到的unique substring是”x”
以”y”结尾的max substring长度是2,对应找到的unique substring是”y”和”xy”
以”z”结尾的max substring长度是3,在后半段连续substring中找到的max长度是2,但小于3,所以总体max substring的长度是3.

    public int findSubstringInWraproundString(String p) {
        if (p.length() < 2) return p.length();
        int[] length = new int[26];
        int len = 0;
        for (int i = 0; i < p.length(); i++) {
            if (i == 0 || p.charAt(i) - 'a' == (p.charAt(i-1) - 'a' + 1) % 26) {
                len++;
            } else {
                len = 1;
            }
            length[p.charAt(i) - 'a'] = Math.max(len, length[p.charAt(i) - 'a']);
        }
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            sum += length[i];
        }
        return sum;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s