LeetCode刷题实战467:环绕字符串中唯一的子字符串
共 2566字,需浏览 6分钟
·
2021-12-18 11:21
We define the string s to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look like this:
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
Given a string p, return the number of unique non-empty substrings of p are present in s.
示例
示例 1:
输入: "a"
输出: 1
解释: 字符串 S 中只有一个"a"子字符。
示例 2:
输入: "cac"
输出: 2
解释: 字符串 S 中的字符串“cac”只有两个子串“a”、“c”。.
示例 3:
输入: "zab"
输出: 6
解释: 在字符串 S 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。.
解题
public int findSubstringInWraproundString(String p) {
int len = p.length();
int[] tabLen = new int[26];// 记录以26个字母结尾的有效字符串个数(去重之后的)
int curLen = 1;// 当前连续字符串(有效)长度,自己单独出现,默认初始值是1
tabLen[p.charAt(0) - 'a'] = 1;
for (int i = 1; i < p.length(); ++i) {
int pre = p.charAt(i - 1) - 'a';
int cur = p.charAt(i) - 'a';
if ((cur - pre + 26) % 26 == 1)
curLen++;
else
curLen = 1;
// 为什么下面是取max?
//比如zaba, 最后一个a单独出现的情况已经在第一个a出现的时候计算过了
// 最后一个a造成的答案长是1,但是第一个a可以造成a,za两个结果
// 所以,对于a这个字符,取最大的也就是第一个a产生的子集
tabLen[cur] = Math.max(tabLen[cur], curLen);
}
int ans = 0;
//累加数组的值得到所有字母结尾有效字符串的和
for (int count : tabLen) ans += count;
return ans;
}
LeetCode刷题实战462:最少移动次数使数组元素相等 II