[LeetCode] 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.

这道题说有一个无限长的封装字符串,然后又给了我们另一个字符串p,问我们p有多少非空子字符串在封装字符串中。我们通过观察题目中的例子可以发现,由于封装字符串是26个字符按顺序无限循环组成的,那么满足题意的p的子字符串要么是单一的字符,要么是按字母顺序的子字符串。这道题遍历p的所有子字符串会TLE,因为如果p很大的话,子字符串很多,会有大量的满足题意的重复子字符串,必须要用到trick,而所谓技巧就是一般来说你想不到的方法。我们看abcd这个字符串,以d结尾的子字符串有abcd, bcd, cd, d,那么我们可以发现bcd或者cd这些以d结尾的字符串的子字符串都包含在abcd中,那么我们知道以某个字符结束的最大字符串包含其他以该字符结束的字符串的所有子字符串,说起来很拗口,但是理解了我上面举的例子就行。那么题目就可以转换为分别求出以每个字符(a-z)为结束字符的最长连续字符串就行了,我们用一个数组cnt记录下来,最后在求出数组cnt的所有数字之和就是我们要的结果啦,参见代码如下:

解法一:
class Solution {
public:
    int findSubstringInWraproundString(string p) {
        vector<int> cnt(26, 0);
        int len = 0;
        for (int i = 0; i < p.size(); ++i) {
            if (i > 0 && (p[i] == p[i - 1] + 1 || p[i - 1] - p[i] == 25)) {
                ++len;
            } else {
                len = 1;
            }
            cnt[p[i] - 'a'] = max(cnt[p[i] - 'a'], len);
        }
        return accumulate(cnt.begin(), cnt.end(), 0);
    }
};

下面这种方法跟上面的基本一样,就是在更新每个最大长度时,把差值累加到结果中,这跟最后统一加上最大值的效果一样,参见代码如下:

解法二:

class Solution {
public:
    int findSubstringInWraproundString(string p) {
        vector<int> cnt(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 > cnt[cur]) {
                res += len - cnt[cur];
                cnt[cur] = len;
            }
        }
        return res;
    }
};

 本文转自博客园Grandyang的博客,原文链接:封装字符串中的独特子字符串[LeetCode] Unique Substrings in Wraparound String ,如需转载请自行联系原博主。

相关文章
|
10天前
|
NoSQL Redis
Redis 字符串(String)
10月更文挑战第16天
26 4
|
7天前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
23 1
|
22天前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
22 9
|
21天前
|
canal 安全 索引
(StringBuffer和StringBuilder)以及回文串,字符串经典习题
(StringBuffer和StringBuilder)以及回文串,字符串经典习题
32 5
|
1月前
|
存储 JavaScript 前端开发
JavaScript 字符串(String) 对象
JavaScript 字符串(String) 对象
38 3
|
22天前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
14 0
|
22天前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
27 0
|
22天前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
15 0
|
22天前
【LeetCode 19】541.反转字符串II
【LeetCode 19】541.反转字符串II
18 0
|
22天前
【LeetCode 18】6.2.反转字符串
【LeetCode 18】6.2.反转字符串
14 0