1.题目描述
把字符串 s 看作是 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，所以 s 看起来是这样的：
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...." .
现在给定另一个字符串 p 。返回 s 中 唯一 的 p 的 非空子串 的数量 。
示例 1:
输入: p = "a"
输出: 1
解释: 字符串 s 中只有一个"a"子字符。
示例 2:
输入: p = "cac"
输出: 2
解释: 字符串 s 中的字符串“cac”只有两个子串“a”、“c”。.
示例 3:
输入: p = "zab"
输出: 6
解释: 在字符串 s 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。
2.思路
2.1 代码
题目要求在字符串中找到连续子数组个数，其实就是在遍历数组时，求以当前字符结尾的连续子串长度，然后再把数组中每一位对应的子串长度加起来求和便是最终答案。这里一下几点需要注意：
- 重复字符的问题。出现重复字符时，对比子串长度，以最长的为结果，并最终结果只计算一次；
- 题目使用环形字符串，因此当遍历到 a 时，如果前一位是 z ，那么就需要在前一位基础上继续往下算，即子串长度继续加 1；
- 当当前位与前一位不连续时，这个时候子串长度应当从 1 开始重新计算
以 “zab” 为例进行说明：
- 遍历 i=0 时，此时以 z 为结尾的连续子串只有 z ，因此统计个数为 1（z）；
- 遍历 i=1 时，此时以 a 为结尾的连续子串为 za，因为是环形数组，所以 z 之后应该继续从 a 开始，此时统计个数为2（a，za）；
- 遍历 i=2 时，此时以 b为结尾的连续子串为 zab，因此统计个数为3（b，ab，zab）；
- 最后将三个字符对应的最长子串个数加起来等于 6 ，便是最终答案。
再以 “aabb” 为例说明存在重复字符时的处理过程：
- 遍历 i=0 时，此时以 a 为结尾的连续子串只有 a ，因此统计个数为 1（a）；
- 遍历 i=1 时，此时以 a 为结尾的连续子串为 a，此时子串个数为 1 ，但是因为前面出现过 a ，两个子串个数都是 1 ，因此以 a 为结尾的连续子串个数为 1（a）；
- 遍历 i=2 时，此时以 b为结尾的连续子串为 ab，因此统计个数为2（b，ab）；
- 遍历 i=3 时，此时以 b 为结尾的连续子串为 b，长度为 1（b），但是前面出现过一次 b，因此选择两个子串中个数较大的作为以 b 结尾的子串，最终结果为 2；
- 遍历完成得到最终答案是 3。
代码中使用一 26 位的数组存放各个字符子串长度，count 统计子串长度，当不连续时，count 重置为 1，代码如下：
class Solution {
public int findSubstringInWraproundString(String p) {
char[] chars = p.toCharArray();
int[] tmp = new int[26];
tmp[chars[0] - 'a'] = 1;
int count = 1;
for (int i = 1; i < chars.length; i++) {
if (chars[i] == chars[i - 1] + 1 || (chars[i] == 'a' && chars[i - 1] == 'z')) {
count++;
} else {
count = 1;
}
tmp[chars[i] - 'a'] = Math.max(count, tmp[chars[i] - 'a']);
}
int ans = 0;
for (int i = 0; i < 26; i++) {
ans += tmp[i];
}
return ans;
}
}
2.2 测试结果
通过测试
测试结果
3.总结
- 题目转换为求以字符结尾的连续子串长度更容易解答
- 使用 tmp 数组统计每一位字符为结尾的连续子数组个数
- 当存在不连续的时候，count 重置为 1
- 这道题其实挺难的，主要很容易陷入惯性思维，从头开始往后迭代进行字符判断，但是一旦把思维转换过来后所有问题都迎刃而解了
