資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究查詢字串的不同子字串中的不同字元
字串是由字元、數字和特殊字元組成的序列。一個字串可能包含多個子字串。給定字串的子字串是按順序取的任何字元序列。它必須滿足以下屬性
所有字元都應取自輸入字串
從原始字串中取出的索引應該是連續的。字元不能跳過。
它可以從原始字串中刪除字元。從特定字串中取出的所有字元都應該具有連續的性質。但是，每個子字串可以由相同或不同的字元組成。在本文中，我們將開發一個 C++ 程式碼來計算給定字串的每個子字串中遇到的不同字元的數量。下面是一個示例，以便您清楚地瞭解這一點：
示例
讓我們考慮示例字串“TART”
子字串 |
不同字元 |
計數 |
|---|---|---|
T |
1 |
1 |
TA |
2 |
3 |
TAR |
3 |
6 |
TART |
3 |
9 |
A |
1 |
10 |
AR |
2 |
12 |
ART |
3 |
15 |
R |
1 |
16 |
RT |
2 |
18 |
T |
NA（由於此子字串已評估） |
18 |
因此，“TART”字串的不同子字串中的總字元數為 18。
可以使用以下方法解決此問題：
set.find(substr) 用於定位指定 substr 是否存在於 set 中
set.size() 用於返回 set 中的專案數。
演算法
步驟 1 - 保持一個 set 資料結構以儲存給定字串的所有子字串。除此之外，還維護一個計數器來跟蹤不同字元的總數。
步驟 2 - 使用外部迴圈遍歷字串。
步驟 3 - 內部迴圈從外部迴圈的位置開始，以便逐個訪問字元並建立子字串。
步驟 4 - 維護另一組字元以新增在當前子字串中遇到的所有不同字元。
步驟 5 - 建立一個臨時子字串變數，並且在每次內部迴圈迭代期間，將字元附加到臨時字串。
步驟 6 - 如果字元不在其中，則將其新增到 set 中。
步驟 7 - 如果找到的子字串不是包含子字串的 set 的一部分，則將其插入並使用 set 的大小遞增計數器，因為它包含所有唯一的字元。
步驟 8 - 否則，計算並評估下一個子字串。
步驟 9 - 返回維護的計數器的值。
示例
以下 C++ 程式碼片段用於將字串作為輸入並計算儲存在唯一子字串中的不同字元：
//getting the required library
#include <bits/stdc++.h>
using namespace std;
//called function to calculate the different characters
int getDistinctChar(string str){
//declaring a set to store substrings of the given string
set<string> substrset;
//maintaining a variable to store the count of distinct char
int cnt = 0;
int len = str.length();
for (int i = 0; i < len; i++) {
//getting the current substring
string substr = "";
//another set to maintain the track of characters encountered in a substring
set<char> charset;
for (int j = i; j < len; j++) {
char ch = str[j];
//adding character to the substring
substr= substr + ch;
//adding the character to the char set
charset.insert(ch);
//check if substring exists in the given set of substrings
if (substrset.find(substr) == substrset.end()) {
//incrementing the counter of distinct characters with the number of characters stored in the charset
int distinctchar = charset.size();
cnt += distinctchar;
//add the new substring to the set
substrset.insert(substr);
}
}
}
return cnt;
}
int main(){
//declaring a sample string
string str = "TART";
//getting a counter
int cnt = getDistinctChar(str);
cout<<"Entered Character : "<<str;
//printing the count of total distinct characters
cout << "\nTotal count of distinct characters in substrings of string :" << cnt;
return 0;
}
輸出
Entered Character : TART Total count of distinct characters in substrings of string :18
結論
給定字串的子字串計算是一個多項式時間演算法。但是，為了獲取不同的子字串和不同的字元，需要一個 set 資料結構來確保沒有重複。所討論方法的時間複雜度本質上是多項式，即 O(n2)，因為迭代兩個迴圈以計算給定字串的所有子字串。上述演算法的空間複雜度為 O(n)，因為維護兩個 set 以跟蹤不同子字串和每個子字串中的字元。
727 次瀏覽
