https://leetcode.com/problems/unique-substrings-in-wraparound-string/
X.
https://leetcode.com/problems/unique-substrings-in-wraparound-string/discuss/95439/Concise-Java-solution-using-DP
针对这道题来说，以一个字符作为字符串的结尾，只要知道连续的长度有多少，那么以这个字符结尾的子串就有多少个，这样只需要遍历一遍就可以了
这道题说有一个无限长的封装字符串，然后又给了我们另一个字符串p，问我们p有多少非空子字符串在封装字符串中。我们通过观察题目中的例子可以发现，由于封装字符串是26个字符按顺序无限循环组成的，那么满足题意的p的子字符串要么是单一的字符，要么是按字母顺序的子字符串。这道题遍历p的所有子字符串会TLE，因为如果p很大的话，子字符串很多，会有大量的满足题意的重复子字符串，必须要用到trick，而所谓技巧就是一般来说你想不到的方法。我们看abcd这个字符串，以d结尾的子字符串有abcd, bcd, cd, d，那么我们可以发现bcd或者cd这些以d结尾的字符串的子字符串都包含在abcd中，那么我们知道以某个字符结束的最大字符串包含其他以该字符结束的字符串的所有子字符串，说起来很拗口，但是理解了我上面举的例子就行。那么题目就可以转换为分别求出以每个字符(a-z)为结束字符的最长连续字符串就行了，我们用一个数组cnt记录下来，最后在求出数组cnt的所有数字之和就是我们要的结果啦
http://blog.csdn.net/caoyan_12727/article/details/53510574
https://discuss.leetcode.com/topic/76020/evolve-from-brute-force-to-optimal
https://www.xiadong.info/2016/12/05/leetcode-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.
X.
https://leetcode.com/problems/unique-substrings-in-wraparound-string/discuss/95439/Concise-Java-solution-using-DP
The idea is, if we know the max number of unique substrings in
p ends with 'a', 'b', ..., 'z', then the summary of them is the answer. Why is that?- The max number of unique substring ends with a letter equals to the length of max contiguous substring ends with that letter. Example
"abcd", the max number of unique substring ends with'd'is 4, apparently they are"abcd", "bcd", "cd" and "d". - If there are overlapping, we only need to consider the longest one because it covers all the possible substrings. Example:
"abcdbcd", the max number of unique substring ends with'd'is 4 and all substrings formed by the 2nd"bcd"part are covered in the 4 substrings already. - No matter how long is a contiguous substring in
p, it is inssinceshas infinite length. - Now we know the max number of unique substrings in
pends with'a', 'b', ..., 'z'and those substrings are all ins. Summary is the answer, according to the question.
public int findSubstringInWraproundString(String p) {
// count[i] is the maximum unique substring end with ith letter.
// 0 - 'a', 1 - 'b', ..., 25 - 'z'.
int[] count = new int[26];
// store longest contiguous substring ends at current position.
int maxLengthCur = 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))) {
maxLengthCur++;
}
else {
maxLengthCur = 1;
}
int index = p.charAt(i) - 'a';
count[index] = Math.max(count[index], maxLengthCur);
}
// Sum to get result
int sum = 0;
for (int i = 0; i < 26; i++) {
sum += count[i];
}
return sum;
}针对这道题来说，以一个字符作为字符串的结尾，只要知道连续的长度有多少，那么以这个字符结尾的子串就有多少个，这样只需要遍历一遍就可以了
http://www.cnblogs.com/grandyang/p/6143071.htmlpublic int findSubstringInWraproundString(String p) {// count[i] is the maximum unique substring end with ith letter.// 0 - 'a', 1 - 'b', ..., 25 - 'z'.int[] count = new int[26];// store longest contiguous substring ends at current position.int maxLengthCur = 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))) {maxLengthCur++;} else {maxLengthCur = 1;}int index = p.charAt(i) - 'a';count[index] = Math.max(count[index], maxLengthCur);}// Sum to get resultint sum = 0;for (int i = 0; i < 26; i++) {sum += count[i];}return sum;}
这道题说有一个无限长的封装字符串，然后又给了我们另一个字符串p，问我们p有多少非空子字符串在封装字符串中。我们通过观察题目中的例子可以发现，由于封装字符串是26个字符按顺序无限循环组成的，那么满足题意的p的子字符串要么是单一的字符，要么是按字母顺序的子字符串。这道题遍历p的所有子字符串会TLE，因为如果p很大的话，子字符串很多，会有大量的满足题意的重复子字符串，必须要用到trick，而所谓技巧就是一般来说你想不到的方法。我们看abcd这个字符串，以d结尾的子字符串有abcd, bcd, cd, d，那么我们可以发现bcd或者cd这些以d结尾的字符串的子字符串都包含在abcd中，那么我们知道以某个字符结束的最大字符串包含其他以该字符结束的字符串的所有子字符串，说起来很拗口，但是理解了我上面举的例子就行。那么题目就可以转换为分别求出以每个字符(a-z)为结束字符的最长连续字符串就行了，我们用一个数组cnt记录下来，最后在求出数组cnt的所有数字之和就是我们要的结果啦
http://blog.csdn.net/caoyan_12727/article/details/53510574
前面的"abc"会出现的子串有：a,b,c,ab,bc,abc;
后面的“abcd”会出现的子串有：a,b,c,d,ab,bc,cd,abc,bcd,abcd,在应用普通方法进行累加的时候，会出现重复统计，当时第一反应是建立一个hashmap，但是这样空间复杂度很大且还要将每一个出现过的子串添加到hashmap中，实现难度较大；
但是，换个角度思考，在字符串种p中，出现的字母也就是26个，如果我们求得以每个字母开头的子串，然后再将它们加起来，就可以得到所有的子串，比如说：
example: xyzabcefg
longest(x) = 6, ==> we get 6 sub strings started from x, x xy xyz xyza xyzab xyzabc
longest(y) = 5 ==> y yz yza yzab yzabc
longest(c) = longest(g) = 1 ==> c, g
longest(x) = 6, ==> we get 6 sub strings started from x, x xy xyz xyza xyzab xyzabc
longest(y) = 5 ==> y yz yza yzab yzabc
longest(c) = longest(g) = 1 ==> c, g
这样问题就可以变得简单了。此时就是如何求得longest(a)。对于上述的"abcabcd"我们可以求得两个以a为开头的所有子串的长度分别是6和10，这时我们会取较大值，因为只要是连续出现的以a为开头的字符串的形式一定是"abcd...xyzabc..."所以长度长的串一定包含长度短的所有子串，就像abcd的子串包含abc的所有子串一样。。。
- int findSubstringInWraproundString(string p) {
- vector<int> letters(26, 0);
- int res = 0, len = 0;
- for (int i = 0; i < p.size(); i++) {
- int cur = p[i] - 'a';
- if (i > 0 && p[i - 1] != (cur + 26 - 1) % 26 + 'a') len = 0;
- if (++len > letters[cur]) {
- res += len - letters[cur];//\\
- letters[cur] = len;
- }
- }
- return res;
- }
Letters[i] represents the longest consecutive substring ended with chr(97+i), update res only when current L is bigger than letters[curr].
int findSubstringInWraproundString(string p) {
vector<int> letters(26, 0);
int res = 0, len = 0;
for (int i = 0; i < p.size(); i++) {
int cur = p[i] - 'a';
if (i > 0 && p[i - 1] != (cur + 26 - 1) % 26 + 'a') len = 0;
if (++len > letters[cur]) {
res += len - letters[cur];
letters[cur] = len;
}
}
return res;
}https://discuss.leetcode.com/topic/76020/evolve-from-brute-force-to-optimal
- O(n^3) check each substr, a hashtable is used to remove duplicate strings.
int findSubstringInWraproundString(string p) {
int n = p.size();
unordered_set<string> ht;
for(int i=0;i<n;i++)
for(int j=i;j<n;j++) {
if(j>i && p[j-1]+1!=p[j] && p[j-1]-p[j]!=25) break;
ht.insert(p.substr(i,j-i+1));
}
return ht.size();
}
- O(n^2 logn), Each valid substr can be represented by the first char and the length, instead of the whole string.
int findSubstringInWraproundString(string p) {
int n = p.size();
set<pair<char,int>> bst;
for(int i=0;i<n;i++)
for(int j=i;j<n;j++) {
if(j>i && p[j-1]+1!=p[j] && p[j-1]-p[j]!=25) break;
bst.insert(pair<char,int>(p[i],j-i+1));
}
return bst.size();
}
- O(n^2). For substrs starting at the same char, we only need to record the longest one. Because it covers all the shorter substrs starting from the char. The length is the number of substrings starting at the char.
int findSubstringInWraproundString(string p) {
int n = p.size(), len[26]={0};
for(int i=0;i<n;i++)
for(int j=i;j<n;j++) {
if(j>i && p[j-1]+1!=p[j] && p[j-1]-p[j]!=25) break;
len[p[i]-'a'] = max(len[p[i]-'a'],j-i+1);
}
return accumulate(len,len+26,0);
}
- O(n). Getting the longest substr starting from each char can be done in linear time. We can use two pointers to keep track of the current valid substring.
int findSubstringInWraproundString(string p) {
int len[26]={0}, i = 0, n = p.size();
for(int j=0;j<n;j++)
if(j>i && p[j-1]+1!=p[j] && p[j-1]-p[j]!=25) {
for(int k=i;k<min(j,i+26);k++) len[p[k]-'a'] = max(len[p[k]-'a'],j-k);
i=j--;
}
for(int k=i;k<min(n,i+26);k++) len[p[k]-'a'] = max(len[p[k]-'a'],n-k);
return accumulate(len,len+26,0);
}https://www.xiadong.info/2016/12/05/leetcode-467-unique-substrings-in-wraparound-string/
dp[i]记录以p[i]为结尾的符合要求的子串的长度. 为了防止重复, 用另一个数组tail以字母为索引保存结果中以某个字母结尾的最长的子串的长度. 当p[i]与p[i-1]是连续的时候, p[i]=p[i-1]; 否则p[i]=1. 再检查tail[p[i]-'a']与dp[i]的大小关系, 若tail[p[i]-'a']>=dp[i], 说明p[i]结尾的所有子串都已经在结果中了; 否则更新tail[p[i]-'a']=dp[i], 增加结果集中以p[i]这个字母结尾的子串的数量. 最后再对tail数组求和就得到结果http://bookshadow.com/weblog/2016/12/04/leetcode-unique-substrings-in-wraparound-string/int findSubstringInWraproundString(string p) {if(p.empty()) return 0;vector<int> dp(p.length(), 0);vector<int> tail(26, 0);dp[0] = 1;tail[p[0] - 'a'] = 1;for(int i = 1; i < p.length(); i++){if((p[i - 1] != 'z' && p[i] == p[i - 1] + 1) || (p[i - 1] == 'z' && p[i] == 'a')){dp[i] = dp[i - 1] + 1;}else{dp[i] = 1;}int index = p[i] - 'a';tail[index] = max(tail[index], dp[i]);}int ans = 0;for(auto i : tail){ans += i;}return ans;}
按照子串的首字母分类计数
用字典cmap记录以某字母开始的子串的最大长度
遍历字符串p，维护区间[start, end]，p[start ... end]是无限循环字符串s的一部分
更新p[start], p[start + 1], ... p[end]在cmap中的长度值
最终结果为cmap中value的和
def findSubstringInWraproundString(self, p):
"""
:type p: str
:rtype: int
"""
pattern = 'zabcdefghijklmnopqrstuvwxyz'
cmap = collections.defaultdict(int)
start = end = 0
for c in range(len(p)):
if c and p[c-1:c+1] not in pattern:
for x in range(start, end):
cmap[p[x]] = max(end - x, cmap[p[x]])
start = c
end = c + 1
for x in range(start, end):
cmap[p[x]] = max(end - x, cmap[p[x]])
return sum(cmap.values())
将上述代码中cmap的含义变更为记录以某字母结尾的子串的最大长度，可以使代码简化。
def findSubstringInWraproundString(self, p):
"""
:type p: str
:rtype: int
"""
pattern = 'zabcdefghijklmnopqrstuvwxyz'
cmap = collections.defaultdict(int)
clen = 0
for c in range(len(p)):
if c and p[c-1:c+1] not in pattern:
clen = 1
else:
clen += 1
cmap[p[c]] = max(clen, cmap[p[c]])
return sum(cmap.values())
http://stackoverflow.com/questions/40955470/unique-substrings-in-wrap-around-strings