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:

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.

解法1:

又是维护一个running local optimal，然后再更新最终答案的题目。
这里是把p中以每一个字符结尾的最长子串加入到hashmap中。
之后再得出一个加和就可以了。
C++

1

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int findSubstringInWraproundString(String p) {
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int maxLen = 0;
        for (int i = 0; i < p.length(); i++) {
            if (i > 0 && (p.charAt(i) - p.charAt(i -1) == 1 || p.charAt(i) - p.charAt(i - 1) == -25)) {
                maxLen++;
            } else {
                maxLen = 1;
            }
            map.put(p.charAt(i), Math.max(map.getOrDefault(p.charAt(i), 0), maxLen));
        }
        int sum = 0;
        for (char key : map.keySet()) {
            sum += map.get(key);
        }
        return sum;        
    }
}