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.
方法
一开始准备使用DFS，发现不仅编码上有问题，估计也会超时。后来想到DP。
首先，对于abcd找子串有如下规律：子串总数为1+2+3+4,即子串个数为累加和。
这个是自己想的dp公式，dp[i]表示在位置i时字符为p[i]时出现的子串个数。
dp[i] = {dp[i-1]+1 {|p[i-1]-p[i]==1|},1}
发现有一个问题，如果出现’abcabcde’的情况还需要判断哪个位置的dp[i]最大，以及对应的起始地点，再求和。这个状态转换方程本人没有用代码验证，如有错误，请大神指正！！！
网上已有大神想出了更好的解决方法，即int[] count = new int[26]，count数组存对应字母最大的子串值，因为对于’abcabcde’，abcde的情况一定包含abc的情况。这样就可以不需要像之前的方程判断起始位置等，直接遍历count即可。状态转换方程为：count[i] = max(count[i],length)，length为对应的累加和
public class Solution {
public int findSubstringInWraproundString(String p) {
int[] count = new int[26];
int maxlength = 0;
for(int i = 0; i < p.length(); i++){
if(i > 0 && (p.charAt(i)-p.charAt(i-1) == 1 || p.charAt(i-1)-p.charAt(i) == 25)){
maxlength++;
}else{
maxlength = 1;
}
int index = p.charAt(i)-'a';
count[index] = Math.max(count[index],maxlength);
}
int num = 0;
for(int i = 0; i < 26; i++){
num = num + count[i];
}
return num;
}
}