a080 - NOI2000 Day2.1.单词查找树

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算給定单词列表所對應的最小单词查找树的節點數。单词查找树的特性是每個節點包含一個大寫字母（根節點除外），從根節點到某個節點的路徑上的字母構成該節點對應的單詞。目標是找到最節省空間的樹結構。

解題思路

這題的核心是利用 Trie (前綴樹) 的概念。我們遍歷輸入的每個單詞，並在 Trie 中插入。如果當前字符在當前節點不存在，則創建一個新的節點，並將節點數加一。如果字符已經存在，則直接移動到相應的節點。這樣，Trie 的結構會自動最小化節點數，因為共享前綴的單詞會共享路徑。

複雜度分析

• 時間複雜度: O(N * M)，其中 N 是單詞的數量，M 是單詞的平均長度。
• 空間複雜度: O(N * M)，最壞情況下，所有單詞都不同，Trie 的空間複雜度與所有單詞的總長度成正比。

程式碼

#include <iostream>
using namespace std;
int ans=1,a[320001][26];
string b;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	while(cin >> b){
		for(int i=0,bl=b.length(),x=0;i<bl;++i){
			if(!a[x][b[i]-'A']){
				++ans;
				a[x][b[i]-'A']=ans;
			}
			x=a[x][b[i]-'A'];
		}
	}
	cout << ans;
}