leetcode 467. Unique Substrings in Wraparound String 连续字符串长度统计+动态规划DP

清疚 2022-06-03 02:28 93阅读 0赞

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.

我们看abcd这个字符串，以d结尾的子字符串有abcd, bcd, cd, d，那么我们可以发现bcd或者cd这些以d结尾的字符串的子字符串都包含在abcd中，那么我们知道以某个字符结束的最大字符串包含其他以该字符结束的字符串的所有子字符串，说起来很拗口，但是理解了我上面举的例子就行。那么题目就可以转换为分别求出以每个字符(a-z)为结束字符的最长连续字符串就行了，我们用一个数组cnt记录下来，最后在求出数组cnt的所有数字之和就是我们要的结果啦。

建议和[leetcode 696. Count Binary Substrings 连续出现相同次数0或1子串数量 + 很棒的做法][leetcode 696. Count Binary Substrings _0_1_ _] 和 [leetcode 673. Number of Longest Increasing Subsequence LISS最长递增子序列数量+动态规划][leetcode 673. Number of Longest Increasing Subsequence LISS]一起学习

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    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);
        }
    };

[leetcode 696. Count Binary Substrings _0_1_ _]: http://blog.csdn.net/jackzhang_123/article/details/78881335
[leetcode 673. Number of Longest Increasing Subsequence LISS]: http://blog.csdn.net/jackzhang_123/article/details/78870425