我在 2020 年 8 月 16 日發生的 Google 編碼挑戰賽中遇到了以下問題。我試圖解決它但沒有成功。字典中有N這樣的詞，每個詞都是固定長度的，并且M只由小寫英文字母組成，即 ('a', 'b', ...,'z')查詢詞記為Q。查詢詞的長度為M。這些單詞包含小寫英文字母，但在某些地方而不是字母之間'a', 'b', ...,'z' 有'?'。請參閱示例輸入部分以了解這種情況。的匹配計數Q，表示為match_count(Q)字典中與查詢詞中的字母?相同位置包含相同英文字母（不包括可位于 位置的字母）的詞的計數Q。換句話說，字典中的單詞可以包含任何位于'?'但其余字母必須與查詢詞匹配。給你一個查詢詞 Q，你需要計算 match_count。輸入格式第一行包含兩個空格分隔的整數N，M分別表示詞典中的單詞數和每個單詞的長度。下一N行包含字典中的每個單詞。下一行包含一個整數 Q，表示您必須為其計算 match_count 的查詢詞的數量。下一Q行每行包含一個查詢詞。輸出格式對于每個查詢詞，match_count在新行中打印特定詞。約束條件1 <= N <= 5X10^41 <= M <= 7 1 <= Q <= 10^5所以，這個問題我有 30 分鐘的時間，我可以編寫以下不正確的代碼，因此沒有給出預期的輸出。
4 回答
萬千封印
TA貢獻1891條經驗 獲得超3個贊
我想我的第一個嘗試是在查詢中用?a替換 the ，即更改為，然后將它們用作正則表達式并將它們與字典中的所有單詞進行匹配，就像這樣簡單：.?at.at
import re
for q in queries:
p = re.compile(q.replace("?", "."))
print(sum(1 for w in words if p.match(w)))
但是，如果輸入大小為 N 到 5x10 4和 Q 到 10 5，這可能太慢了，就像比較所有單詞和查詢對的任何其他算法一樣。
另一方面，請注意M，每個單詞的字母數是恒定的且相當低。因此，您可以為所有位置的所有字母創建 Mx26 組單詞，然后獲取這些組的交集。
from collections import defaultdict
from functools import reduce
M = 3
words = ["cat", "map", "bat", "man", "pen"]
queries = ["?at", "ma?", "?a?", "??n"]
sets = defaultdict(set)
for word in words:
for i, c in enumerate(word):
sets[i,c].add(word)
all_words = set(words)
for q in queries:
possible_words = (sets[i,c] for i, c in enumerate(q) if c != "?")
w = reduce(set.intersection, possible_words, all_words)
print(q, len(w), w)
在最壞的情況下（一個查詢具有?字典中大多數或所有單詞共有的非字母），這可能仍然很慢，但過濾單詞應該比為每個查詢迭代所有單詞快得多。（假設單詞和查詢中都有隨機字母，第一個字母的單詞集將包含 N/26 個單詞，前兩個字母的交集有 N/262 個單詞，等等。）
通過考慮不同的情況，這可能會有所改善，例如（a）如果查詢不包含任何?，只需檢查它是否在set單詞的（?。┲卸粍摻ㄋ羞@些交集；(b) 如果查詢是all- ?，只返回所有單詞的集合；(c) 按大小對可能詞集進行排序，并首先開始與最小集的交集，以減少臨時創建的集的大小。
關于時間復雜度：老實說，我不確定這個算法的時間復雜度是多少。N、Q 和 M 分別是單詞數、查詢數以及單詞和查詢的長度，創建初始集的復雜度為 O(N*M)。之后，查詢的復雜性顯然取決于查詢中非查詢的數量?（以及要創建的集合交集的數量）以及集合的平均大小。對于具有零個、一個或 M 個非?字符的查詢，查詢將在 O(M) 內執行（評估情況，然后進行單個集合/字典查找），但對于具有兩個或更多非字符的查詢?-字符，第一組交集的平均復雜度為 O(N/26)，嚴格來說仍然是 O(N)。（以下所有交叉點只需要考慮 N/262、N/263 等元素，因此可以忽略不計。）我不知道這與 Trie 方法相比如何，如果其他任何答案可以詳細說明，我將非常感興趣在那上面。
HUWWW
TA貢獻1874條經驗 獲得超12個贊
這道題可以借助 Trie 數據結構來完成。首先將所有單詞添加到 trie ds。然后你必須看看這個詞是否存在于 trie 中，有一個特殊條件 ' ?'?所以你也必須注意這種情況，比如角色是？然后只需轉到單詞的下一個字符。
慕田峪4524236
TA貢獻1875條經驗 獲得超5個贊
它應該是 O(N) 時間和空間方法，因為 M 很小并且可以被認為是常數。您可能想在這里查看 Trie 的實現。
執行第一遍并將單詞存儲在 Trie DS 中。
接下來對于您的查詢，您按以下順序執行 DFS 和 BFS 的組合。
如果您收到 ?，請執行 BFS 并添加所有孩子。對于非 ?，執行 DFS，這應該指向一個詞的存在。
為了進一步優化，還可以使用后綴樹來存儲DS。
蝴蝶刀刀
TA貢獻1801條經驗 獲得超8個贊
您可以使用簡化版的 trie，因為查詢字符串具有預定義的長度。endsTrie 節點中不需要變量
#include <bits/stdc++.h>
using namespace std;
typedef struct TrieNode_ {
struct TrieNode_* nxt[26];
} TrieNode;
void addWord(TrieNode* root, string s) {
TrieNode* node = root;
for(int i = 0; i < s.size(); ++i) {
if(node->nxt[s[i] - 'a'] == NULL) {
node->nxt[s[i] - 'a'] = new TrieNode;
}
node = node->nxt[s[i] - 'a'];
}
}
void matchCount(TrieNode* root, string s, int& cnt) {
if(root == NULL) {
return;
}
if(s.empty()) {
++cnt;
return;
}
TrieNode* node = root;
if(s[0] == '?') {
for(int i = 0; i < 26; ++i) {
matchCount(node->nxt[i], s.substr(1), cnt);
}
}
else {
matchCount(node->nxt[s[0] - 'a'], s.substr(1), cnt);
}
}
int main() {
int N, M;
cin >> N >> M;
vector<string> s(N);
TrieNode *root = new TrieNode;
for (int i = 0; i < N; ++i) {
cin >> s[i];
addWord(root, s[i]);
}
int Q;
cin >> Q;
for(int i = 0; i < Q; ++i) {
string queryString;
int cnt = 0;
cin >> queryString;
matchCount(root, queryString, cnt);
cout << cnt << endl;
}
}
添加回答
舉報
0/150
提交
取消