leetcode 467. 环绕字符串中唯一的子字符串

绝地灬酷狼 2023-07-03 13:28 3阅读 0赞

思路：首先要读懂题意。题意是有一个循环字符串s（abc...zabc...），给一个p。问p的子串中，有多少个也是s的子串。

例如cac中，子串有c,ca,ac,cac，a  但是，同时也是s的子串的，只要c,a.  因为s字符串里没有ca相邻的。

其实这是一个简单的递推。dp\[i\]表示以p\[i\]结尾是子串有多少个,如果p\[i\]与p\[i-1\]在s中相邻，那么dp\[i\]=dp\[i-1\]+1

否则dp\[i\]=1 (单独一个字符，一定在s里面)

为了去除重复的。例如zabab。我们设sum\[i\]表示以'a'+i 字母结尾的子串个数。sum\[i\]只要去p字符中对应字符的最大值即可（倘若有小的，那一定是重复的）。

写的有点乱。直接看代码。

class Solution {
    public:
        int findSubstringInWraproundString(string p) {
            int n=p.size();
            if(n==0) return 0;
            int dp[n+3];
            memset(dp,0,sizeof(dp));
            dp[1]=1;
            int sum[27];
            memset(sum,0,sizeof(sum));
            sum[(p[0]-'a'+1)%26]=1;
            for(int i=2;i<=n;i++)
            {
                int tmp1=(p[i-2]-'a'+1)%26;
                int tmp2=(p[i-1]-'a'+1)%26;
                //cout<<tmp1<<" "<<tmp2<<endl;
                if((tmp1+1)%26==tmp2)
                {
                    dp[i]=dp[i-1]+1;
                }
                else
                {
                    dp[i]=1;
                }
                //cout<<dp[i]<<endl;
                sum[tmp2]=max(sum[tmp2],dp[i]);
            }
            int ans=0;
            for(int i=0;i<26;i++)
            {
                ans+=sum[i];
            }
            return ans;
        }
    };