資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學長度為 K 的公共字首字串的最大數量
在這個問題中，我們需要計算具有長度為 K 的公共字首的最大字串數。我們可以從所有字串中提取長度為 K 的字首，並使用 map 資料結構計算相似字首的最大數量。此外，我們還可以使用 Trie 資料結構來解決這個問題。
問題陳述 - 我們給定一個包含多個字串的 strs[] 陣列。我們需要計算包含長度為 K 的公共字首的字串的最大數量。
示例
輸入
strs = {"tutorialspoint", "tut", "abcd", "tumn", "tutorial", "PQR", "ttus", "tuto"};
K = 3;
輸出
4
解釋 - 這 4 個字串包含長度為 3 的公共字首 'tut'。
輸入
strs = {"tutorialspoint", "tut", "abcd", "tumn", "tutorial", "PQR", "ttus", "tuto"};
K = 8;
輸出
2
解釋 - 只有 2 個字串包含相同的長度為 8 的字首，即 'tutorial'。
輸入
strs = {"tutorialspoint", "tut", "abcd", "tumn", "tutorial", "PQR", "ttus", "tuto"};
K = 8;
輸出
1
解釋 - 陣列不包含長度為 2 的公共字首的字串。因此，我們可以輸出 1。
方法 1
在這種方法中，我們將使用 map 資料結構來計算每個子字串長度為 K 的字首的頻率。最後，我們取頻率最高的字首作為輸出。
演算法
步驟 1 - 將 'ans' 初始化為 0，用於儲存具有公共字首的最大字串數。此外，定義 'pref' map 來儲存字串字首的頻率。
步驟 2 - 開始遍歷字串。
步驟 3 - 從 0 開始獲取長度為 K 的子字串，並將其儲存到 'temp' 字串中。
步驟 4 - 在 map 中將 'temp' 的頻率加 1。
步驟 5 - 從 'ans' 和 'temp' 字串的頻率中獲取最大值。
步驟 6 - 最後，返回 'ans' 值。
示例
#include <bits/stdc++.h>
using namespace std;
int getMaxStrs(vector<string> strs, int K) {
int ans = 0;
// Map to store prefix of length K
map<string, int> pref;
// Traverse string
for (int p = 0; p < strs.size(); p++) {
// Taking substring of length K
string temp = strs[p].substr(0, K);
// Insert the prefix into the map
pref[temp]++;
// Get the maximum answer
ans = max(ans, pref[temp]);
}
return ans;
}
int main() {
vector<string> strs = {"tutorialspoint", "tut", "abcd", "tumn", "tutorial", "PQR", "ttus", "tuto"};
int K = 3;
cout << "The number of strings having a common prefix of length K is " << getMaxStrs(strs, K);
return 0;
}
輸出
The number of strings having a common prefix of length K is 4
時間複雜度 - 遍歷字串為 O(N)。
空間複雜度 - 在 map 中儲存字首的頻率為 O(N)。
方法 2
在這種方法中，我們將使用 Trie 資料結構來查詢具有公共字首的最大字串數。我們將所有字串的字首插入到 Trie 中，並檢查它是否出現次數最多。
演算法
步驟 1 - 初始化 Trie 的節點，該節點包含長度為 26 的陣列，指向當前節點的每個字母字元，並將 'cnt' 變數初始化為 0，表示公共字首的數量。
步驟 2 - 開始遍歷陣列的每個字串，並執行 insertNode() 函式以將字串長度為 K 的字首插入到 Trie 中。此外，將 'ans' 變數作為引用傳遞，以儲存具有公共字首的最大字串數。
步驟 3 - 在 insertNode() 函式中，使用 'head' 節點初始化 'temp' 節點，並遍歷字串以將其字首插入到 Trie 中。
步驟 4 - 使用 toLower() 方法將字元轉換為小寫。
步驟 5 - 如果 temp 節點的 'chars' 陣列的 (ch - 'a') 索引為空，則將其賦值為新節點。
步驟 6 - 將 temp->chars[ch - 'a'] 節點的 'cnt' 加 1。
步驟 7 - 如果 p + 1 等於 K，則我們將長度為 K 的字首插入到 Trie 中。因此，使用 'ans' 和 temp->chars[ch - 'a']->cnt 的最大值更新 'ans'，並中斷迴圈。
步驟 8 - 將 temp 節點移動到下一個節點。
步驟 9 - 最後，列印 'ans' 值。
示例
#include <bits/stdc++.h>
using namespace std;
struct Node {
Node *chars[26];
int cnt = 0;
};
Node* head;
void insertNode(string &str, int K, int &ans) {
// Temporary node
Node *temp = head;
// Traverse string characters
for (int p = 0; p < str.size(); p++) {
// Change character to lowercase
char ch = tolower(str[p]);
// If the node does not exist for the current character, initialize it
if (temp->chars[ch - 'a'] == NULL) {
temp->chars[ch - 'a'] = new Node();
}
// Increase count to increment the length of the prefix
temp->chars[ch - 'a']->cnt++;
// If p + 1 is equal to K, then get the maximum result and break the loop.
if (p + 1 == K) {
ans = max(ans, temp->chars[ch - 'a']->cnt);
break;
}
// Go to the next pointer
temp = temp->chars[ch - 'a'];
}
}
int main() {
vector<string> strs = {"tutorialspoint", "tut", "abcd", "tumn", "tutorial", "PQR", "ttus", "tuto"};
int K = 3;
int ans = 0;
// Node initialization
head = new Node();
// Insert all the strings into Trie
for (auto str : strs) {
insertNode(str, K, ans);
}
cout << "The number of strings having a common prefix of length K is " << ans;
return 0;
}
輸出
The number of strings having a common prefix of length K is 4
時間複雜度 - O(N*K)，其中 N 是陣列長度，K 是字首長度。
空間複雜度 - 在 Trie 中儲存所有字串為 O(N*K)。
第一種方法更有效，並且對於初學者更容易理解。第二種方法可能比較複雜，但學習 Trie 資料結構的概念是必要的。
瀏覽量 128
