数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中环绕字符串中的唯一子字符串
假设我们有字符串 s 是无限环绕字符串“abcdefghijklmnopqrstuvwxyz”，因此 s 的值看起来如下 −“...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....”。
现在我们有另一个字符串 p。我们的任务是找出 s 中有多少个唯一的非空子字符串存在于 p 中。具体而言，我们的输入是字符串 p，我们需要输出字符串 s 中 p 的所有不同的非空子字符串的数量。
因此，如果输入类似于“zab”，则输出将为 6。字符串“zab”在字符串 s 中有 6 个子字符串“z”、“a”、“b”、“za”、“ab”、“zab”。
为此，我们将按照以下步骤进行 −
创建一个大小为 26 的数组 dp，将 x := 0
对于 0 到 p 的大小范围内的 I
如果 i > 0 并且 (p[i] – p[i – 1] 为 1 或 p[i – 1] – p[i] 为 25)，则将 x 增加 1，否则将 x 设置为 1
dp[p[i] – ‘a’的 ASCII 码] := 介于 (x，dp[p[i] – ‘a’的 ASCII 码]) 之间的值
ret := 0
对于 0 到 25 范围内的 I
ret := ret + dp[i]
返回 ret
示例 (C++)
让我们看看以下实现以获得更好的理解 −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findSubstringInWraproundString(string p) {
vector <int> dp(26);
int x = 0;
for(int i = 0; i < p.size(); i++){
if(i > 0 && (p[i] - p[i - 1] == 1 || p[i - 1] - p[i] == 25)){
x++;
}
else x = 1;
dp[p[i] - 'a'] = max(x, dp[p[i] - 'a']);
}
int ret = 0;
for(int i = 0; i < 26; i++){
ret += dp[i];
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.findSubstringInWraproundString("zab"));
}输入
"zab"
输出
6
更新日期：29-Apr-2020
192 次浏览
广告