算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 环绕字符串中唯一的子字符串,我们先来看题面:
https://leetcode-cn.com/problems/unique-substrings-in-wraparound-string/
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.
把字符串 s 看作是“abcdefghijklmnopqrstuvwxyz”的无限环绕字符串,所以 s 看起来是这样的:
"...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".
现在我们有了另一个字符串 p 。你需要的是找出 s 中有多少个唯一的 p 的非空子串,尤其是当你的输入是字符串 p ,你需要输出字符串 s 中 p 的不同的非空子串的数目。
注意: p 仅由小写的英文字母组成,p 的大小可能超过 10000。
示例 1:
输入: "a"
输出: 1
解释: 字符串 S 中只有一个"a"子字符。
示例 2:
输入: "cac"
输出: 2
解释: 字符串 S 中的字符串“cac”只有两个子串“a”、“c”。.
示例 3:
输入: "zab"
输出: 6
解释: 在字符串 S 中有六个子串“z”、“a”、“b”、“za”、“ab”、“zab”。.
https://blog.csdn.net/qq_43778308/article/details/108355242
以字符b结尾的字符串的子串,就是以b结束的连续字符串的长度和,比如:zab
z长度是1; za在s中连续,以a结尾长度是2;zab在s中连续,以b结尾长度是3,那么答案就是1+2+3
如果是zabf,前三个长度不变,f之前是b (不连续),则以f结尾连续子串长度是1,答案就是1+2+3+1
所以我们统计连续字符长度,然后累加就好了。
但是注意的是,我们只保存一个字符最长的连续长度,
比如 zabcb, 第一个b连续长度3,第二个是1;我们就只保存那个3,忽略1;
我们创建一个数组tabLen[26]来保存a~z单个字符串结尾的数量
比如tabLen[0]表示a字母结尾的字符串的数量有多少。
通过设置一个临时变量curLen来储存当前遍历到的p[i]字母结尾字符串的数量,
比较一下是不是比上次记录的字符串数量还多,如果更多就更新tabLen[p[i]-'a']的值;
经过一次遍历之后,数组中就储存了所有a~z所有的字母结尾的字符串数量
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;
}
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。
上期推文: