資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究針對 Q 個查詢，統計陣列中具有給定字首的字串數量
在這個問題中，我們將統計每個查詢字串中包含查詢字串作為字首的字串數量。
我們可以遍歷查詢字串列表，並針對每個查詢找到包含它作為字首的字串數量。此外，我們還可以使用 Trie 資料結構來解決此問題。
問題陳述 – 我們給定了一個 strs[] 和 queStr[] 字串陣列，分別包含 N 和 Q 個字串。我們需要統計 Strs[] 陣列中包含 queStr[i] 字串作為每個 queStr[] 陣列字串字首的字串數量。
示例
輸入
strs = {"tutorial", "tutorials", "tutorialspoint", "tut", "pqe"}; queStr = {"tutorials",
"tuto", "pq"};
輸出
2, 3, 1
“tutorials” 和 “tutorialspoint” 包含 “tutorials” 查詢作為字首。
“tutorial”、 “tutorials” 和 “tutorialspoint” 包含 “tuto” 查詢字串作為字首。
只有 “pqe” 字串包含 “pq” 字串作為字首。
輸入
strs = {"abcd", "abe", "abp", "rew", "wel"}; queStr = {"ab", "abn", "mo"};
輸出
3, 0, 0
解釋
“abcd”、 “abe” 和 “abp” 字串包含 “ab” 作為字首。
任何字串都不包含 “abn” 和 “mo” 作為字首。
輸入
strs = {"aaa", "aaa", "aaa"}; queStr = {"a", "aa", "aaa"};
輸出
3, 3, 3
解釋 - 所有字串都包含所有查詢作為字首。
方法 1
在這種方法中，我們將遍歷查詢陣列。我們可以遍歷每個查詢的字串陣列並統計包含該查詢作為字首的字串。要檢查字串是否包含該查詢作為字首，我們可以從字串中獲取等於查詢長度的子字串，並將其與查詢進行匹配。
演算法
步驟 1 - 建立一個名為 “counts” 的列表。
步驟 2 - 開始遍歷 queStr[] 查詢陣列，並在每次迭代中將 “cnt” 初始化為 0。
步驟 3 - 開始遍歷 strs[] 陣列，如果字串大小小於查詢大小，則轉到下一輪迭代。
步驟 4 - 使用 substr() 方法從第 0 個索引獲取子字串，長度等於查詢的長度。如果子字串等於查詢，則將 “cnt” 值加 1。
步驟 5 - 將 “cnt” 值插入 “counts” 列表。
步驟 6 - 返回 “counts” 列表。
示例
#include <bits/stdc++.h>
using namespace std;
vector<int> findPrefixCounts(vector<string> &strs, vector<string> &queStr) {
vector<int> counts;
for (string que : queStr) {
// To store count of string containing x as prefix
int cnt = 0;
for (string str : strs) {
// For query's greater length than string
if (str.size() < que.size()) {
continue;
}
// For string containing query as prefix
if (str.substr(0, que.size()) == que) {
cnt++;
}
}
// Insert count to vector
counts.push_back(cnt);
}
return counts;
}
int main() {
// List of strings and Queries
vector<string> strs = {"tutorial", "tutorials", "tutorialspoint", "tut", "pqe"};
vector<string> queStr = {"tutorials", "tuto", "pq"};
vector<int> counts = findPrefixCounts(strs, queStr);
// Printing the counts
for (int cnt : counts) {
cout << cnt << ", ";
}
return 0;
}
輸出
2, 3, 1,
時間複雜度 - O(N*Q*S)，其中 N 是字串陣列的長度，Q 是查詢陣列的長度，S 是獲取子字串的字串的最大長度。
空間複雜度 - O(Q) 用於儲存每個查詢的計數。
方法 2
我們將使用 Trie 資料結構來解決此方法中的問題。Trie 被稱為字首樹，我們可以用它在大型資料集中搜索字串。
它在每個節點儲存字元，根節點包含空字串。在這裡，我們將使用連結串列來建立 Trie。此外，我們還將為每個節點儲存字元和分支計數。
我們將字首計數儲存到每個節點，表示包含相同字首的字串數量。之後，在查詢查詢作為字首時，我們可以使用查詢字串最後一個字元的字首計數作為答案。
演算法
步驟 1 - 建立一個名為 “treeNode” 的結構體，表示 Trie 資料結構的節點。
步驟 2 - 在節點內部定義 “prefCnt” 變數和型別為 “trieNode” 的陣列，該陣列的大小等於 26。此外，使用建構函式將 “prefCnt” 初始化為 0，並將所有陣列元素初始化為 Null。
步驟 3 - 定義 createTrie() 函式來構建 Trie。
步驟 3.1 - 在 createTrie() 函式中定義 “temp” 節點。
步驟 3.2 - 遍歷陣列的每個字串，並將 “temp” 節點初始化為 “head”。此外，遍歷字串字元。
步驟 3.3 - 在 temp 節點中，如果陣列在等於字元值的索引處包含 null，則在該索引處新增一個新節點。
步驟 3.4 - 將 “temp” 節點的 “prefCnt” 加 1。
步驟 3.5 - 根據字串的當前字元更新 temp 節點。
步驟 4 - 初始化 “res” 列表以儲存包含查詢作為字首的字串計數。
步驟 5 - 執行 createList() 函式以初始化 Trie。
步驟 6 - 對於每個查詢，執行 findQuery() 函式以獲取計數並將其插入 “res” 列表。
步驟 6.1 - 在 findQuery() 函式中，開始遍歷 Trie。
步驟 6.2 - 如果陣列在當前節點中等於字元值的索引處包含 null，則返回 0。
步驟 6.3 - 根據當前字串字元更新 head。
步驟 6.4 - 返回 head 節點的 “prefCnt” 值。
示例
#include <bits/stdc++.h>
using namespace std;
int len;
// Trie node
struct trieNode {
// To store the count of a string with the current prefix
int prefCnt;
trieNode *ch[26];
// Constructor
trieNode() {
prefCnt = 0;
for (int p = 0; p < 26; p++)
ch[p] = NULL;
}
};
void createTrie(vector<string> &list, trieNode *head) {
// Creating the temporary node
trieNode *temp;
for (int p = 0; p < len; p++) {
temp = head;
// Inserting the string in trieNode
for (int q = 0; q < list[p].size(); q++) {
if (temp->ch[list[p][q] - 'a'] == NULL)
temp->ch[list[p][q] - 'a'] = new trieNode();
temp->ch[list[p][q] - 'a']->prefCnt += 1;
temp = temp->ch[list[p][q] - 'a'];
}
}
}
int findQuery(string str, trieNode *head) {
for (int p = 0; p < str.size(); p++) {
if (head->ch[str[p] - 'a'] == NULL)
return 0;
head = head->ch[str[p] - 'a'];
}
return head->prefCnt;
}
vector<int> findPrefixCounts(int strs_len, int que_len,
vector<string> &list, vector<string> &query) {
vector<int> res;
len = strs_len;
trieNode *head = new trieNode();
// Create a trie
createTrie(list, head);
// Finding the count of a string with the current prefix value
for (int p = 0; p < que_len; p++) {
res.push_back(findQuery(query[p], head));
}
return res;
}
// Driver Code
int main() {
// List of strings and Queries
vector<string> strs = {"tutorial", "tutorials", "tutorialspoint", "tut",
"pqe"};
vector<string> queStr = {"tutorials", "tuto", "pq"};
vector<int> counts = findPrefixCounts(strs.size(), queStr.size(), strs,
queStr);
// Printing the counts
for (int cnt : counts) {
cout << cnt << ", ";
}
return 0;
}
輸出
2, 3, 1,
時間複雜度 - (Q*p + N*R)，其中 Q 是查詢總數，N 是字串總數，p 是最長查詢的長度，R 是插入 Trie 的最長字串的長度。
空間複雜度 - O(Q + N*26) 用於儲存等於查詢數量的計數，並建立每個節點包含大小等於 26 的陣列的 Trie。
我們使用了 Trie 資料結構來有效地解決問題。每當我們需要根據字串字首獲取輸出時，都可以使用 Trie 資料結構。
193 次檢視
