azl397985856/leetcode

【每日一题】- 2020-09-15 - 467. 环绕字符串中唯一的子字符串

azl397985856 opened this issue · 3 comments

azl397985856 commented

把字符串 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”。.
 

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-substrings-in-wraparound-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

ZHAOXIN009 commented

C++ 题解;
只记录以独特字符结尾的子串的最大长度,所有26个字符结尾的字串的数量和就是最终结果.

执行用时：8 ms, 在所有 C++ 提交中击败了93.71%的用户
内存消耗：7.3 MB, 在所有 C++ 提交中击败了73.02%的用户

class Solution {
public:
    
    int findSubstringInWraproundString(string p) {
        vector<int>dp(26, 0);
        int sum=0;
        for(int i=0; i<p.size(); ++i){
            if(i>0 && (p[i]==p[i-1]+1||(p[i]=='a'&&p[i-1]=='z')) ){
                sum++;
            }
            else{
                sum=1;
            }
            dp[p[i]-'a']=max(dp[p[i]-'a'], sum);
        }
        return accumulate(dp.begin(), dp.end(), 0);
    }
};
azl397985856 commented

思路

乍一看题目和最长上升子序列差不多， 但是：

  1. 这道题有了首尾相连， 这难不倒我们
  2. 这道题需要是连续的
  3. 这道题相邻的两个数差值为 1，而最长上升子序列的差值是任意正整数（你可以把字母映射到 ascii code）

关于最长上升子序列 ，我写了一个专题，有兴趣的可以看下。 穿上衣服我就不认识你了？来聊聊最长上升子序列

也就是说这题根本不需要用到最长上升子序列的思路。

我刚开始的思路是能不能通过数学法来降维打击，想了想无果。 只能思考别的方法。

由于 p 的数据范围是 10^5 ，因此暴力找出所有子串就需要 10^10 次操作了，应该会超时。而且题目很多信息都没用到，肯定不对。

算法：

  • 定义一个 len_mapper。key 是 字母， value 是 长度。 含义是以 key 结尾的最长连续子串的长度。

关键字是：最长

  • 用一个变量 w 记录连续子串的长度，遍历过程根据 w 的值更新 len_mapper
  • 返回 len_mapper 中所有 value 的和。

比如: abc，此时的 len_mapper 为:

{
 c: 3
 b: 2
 a: 1
}

比如：abcab，此时的len_mapper 依旧。

比如: abcazabc，此时的len_mapper：

{
 c: 4
 b: 3
 a: 2
 z: 1
}

这就得到了去重的目的。

这种算法是不重不漏的，因为最长的连续子串一定是包含了比它短的连续子串，这个**和 1297. 子串的最大出现次数 剪枝的方法有异曲同工之妙。

代码（Python）

class Solution:
    def findSubstringInWraproundString(self, p: str) -> int:
        p = '^' + p
        len_mapper = collections.defaultdict(lambda: 0)
        w = 1
        for i in range(1,len(p)):
            if ord(p[i])-ord(p[i-1]) == 1 or ord(p[i])-ord(p[i-1]) == -25:
                w += 1
            else:
                w = 1
            len_mapper[p[i]] = max(len_mapper[p[i]], w)
        return sum(len_mapper.values())

复杂度分析

  • 时间复杂度：$O(N)$,其中 N 为 P 的长度。
  • 空间复杂度：$O(N)$,其中 N 为 P 的长度。

更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经35K star啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

stale commented

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.