f463 - Cellphone Typing
題目描述
題目描述了一種手機輸入法，它會根據字典自動補全單詞。目標是計算在給定字典下，輸入字典中所有單詞的平均擊鍵次數。如果一個前綴在字典中唯一確定了下一個字符，則該字符會自動輸入，無需用戶擊鍵。
解題思路
本題的核心思想是利用 Trie 樹來高效地查詢字典，並模擬手機輸入法的自動補全過程。
- 構建 Trie 樹: 將字典中的所有單詞插入到 Trie 樹中。在插入過程中，記錄每個節點的子節點數量（
ct）以及是否為一個單詞的結尾（has）。 - 計算擊鍵次數: 對於字典中的每個單詞，從根節點開始遍歷，模擬輸入過程。如果當前節點的子節點數量為 1 且不是單詞結尾，則表示下一個字符可以自動補全，無需擊鍵。否則，需要擊鍵。
- 計算平均擊鍵次數: 統計所有單詞的總擊鍵次數，然後除以單詞的數量，得到平均擊鍵次數。
複雜度分析
- 時間複雜度: O(N * M)，其中 N 是字典中單詞的數量，M 是單詞的平均長度。構建 Trie 樹需要 O(N * M) 的時間，遍歷每個單詞計算擊鍵次數也需要 O(N * M) 的時間。
- 空間複雜度: O(N * M)，Trie 樹的空間複雜度取決於字典中所有單詞的總長度。在最壞情況下，所有單詞都具有不同的前綴，導致 Trie 樹的節點數量與總長度成正比。
程式碼
#include <bits/stdc++.h>
using namespace std;
int n;
string a[100005];
struct trie{
int ct=0;
bool has=0;
trie* nxt[26];
};
int main(){
cin.tie(0);cout.tie(0); ios::sync_with_stdio(0);
while(cin >> n){
int v=0;
trie* root = new trie();
for(int i=0;i<n;++i){
cin >> a[i];
v+=a[i].size();
trie* it=root;
for(int j=0;j<a[i].size();++j){
if(it->nxt[a[i][j]-'a']==nullptr){
++it->ct;
it->nxt[a[i][j]-'a']=new trie();
}
it=it->nxt[a[i][j]-'a'];
if(j==a[i].size()-1)it->has=1;
}
}
for(int i=0;i<n;++i){
trie* it=root;
for(int j=0;j<a[i].size();++j){
if(it->ct==1&&it->has==0&&j)--v;
it=it->nxt[a[i][j]-'a'];
}
}
double ans=round((double)v/(double)n*100)/100;
cout << fixed << setprecision(2) << ans << "\n";
}
}