資料結構
網路
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 次瀏覽
廣告