Hihocode Trieツリーコード

3739 ワード

今日ACはHiHocodeの2番目の問題をつけて、hihocodeはテストのヒントを与えないため、難易度はleetcodeが少し高いと感じて、比較的に気持ち悪いです.
でもACが出てきたときは本当に嬉しかったです.くだらないことは言わないで、本題に入ります.
私は華やかな分割線です!
==============================================================
hihocodeは善意にヒントを提供し、3つに分かれていますが、ポイントは2つです.
1つは、ツリーをどのように構築するかです.
二つ目は、前置単語をどのように検索するかです.
Trieツリーはエッジで文字を保存していますが、ブロガーは最初はノードが保存していると勘違いしていて、少し頭がかかりました.
また,hihocodeは挿入しながら統計する必要があることを示唆し,我々の構造体はこのように現れた.
注意しなければならないのはhihocode定義の重複する単語を2つ計算して、ブロガーは最初に重複する単語を削除して、そこでWAは長い間です.
struct Node
{
	bool isWord;
	Node *child[Max];//save edge
	int L[Max];//save count

	Node()
	{
		isWord = false;

		for (int i = 0; i < Max; i++)
		{
			child[i] = NULL;			
		}

		for (int i = 0; i < Max; i++)
		{
			L[i] = 0;
		}
	}

	~Node()
	{
		for (int i = 0; i < Max; i++)
		{
			delete child[i];
		}
	}
};

単語を挿入:
void Insert(string word)
{
	Node *tempRoot = root;
	for (int i = 0; i < word.length(); i++)
	{
		tempRoot->L[word[i]-'a']++;
		if (tempRoot->child[word[i]-'a'] != NULL)
		{			
			tempRoot = tempRoot->child[word[i]-'a'];
		}
		else
		{
			Node *newNode = new Node();
			tempRoot->child[word[i]-'a'] = newNode;
			tempRoot = tempRoot->child[word[i]-'a'];
		}
		if (i == word.length() - 1)
		{
			if (tempRoot->isWord == false)
			{
				tempRoot->isWord = true;
			}			
		}
	}
}

検索しながら集計しているので、実はtrieツリーに完全に合わなくてもいいし、単語のそのノードがマークしなくても結果に影響しない
単語/接頭辞の検索数:
int find(string word)
{
	Node *tempRoot = root;
	for (int i = 0; i < word.length(); i++)
	{
		if (tempRoot->child[word[i]-'a'] == NULL)return 0;
		else
		{			
			if (i == word.length() - 1) return tempRoot->L[word[i]-'a'];
			tempRoot = tempRoot->child[word[i]-'a'];
		}
	}
}

次にすべてのコードを貼り付けます
すべてのコードには、重複する単語を減算する関数が含まれていますが、使用されません.
#include
#include
using namespace std;

const int Max = 26;
struct Node
{
	bool isWord;
	Node *child[Max];//save edge
	int L[Max];//save count

	Node()
	{
		isWord = false;

		for (int i = 0; i < Max; i++)
		{
			child[i] = NULL;			
		}

		for (int i = 0; i < Max; i++)
		{
			L[i] = 0;
		}
	}

	~Node()
	{
		for (int i = 0; i < Max; i++)
		{
			delete child[i];
		}
	}
};

Node * root = new Node();

void minusDuplicate(string word)
{
	Node *tempRoot = root;
	for (int i = 0; i < word.length(); i++)
	{
		tempRoot->L[word[i]-'a']--;
		tempRoot = tempRoot->child[word[i]-'a'];
	}
}

void Insert(string word)
{
	Node *tempRoot = root;
	for (int i = 0; i < word.length(); i++)
	{
		tempRoot->L[word[i]-'a']++;
		if (tempRoot->child[word[i]-'a'] != NULL)
		{			
			tempRoot = tempRoot->child[word[i]-'a'];
		}
		else
		{
			Node *newNode = new Node();
			tempRoot->child[word[i]-'a'] = newNode;
			tempRoot = tempRoot->child[word[i]-'a'];
		}
		if (i == word.length() - 1)
		{
			if (tempRoot->isWord == false)
			{
				tempRoot->isWord = true;
			}			
		}
	}
}

int find(string word)
{
	Node *tempRoot = root;
	for (int i = 0; i < word.length(); i++)
	{
		if (tempRoot->child[word[i]-'a'] == NULL)return 0;
		else
		{			
			if (i == word.length() - 1) return tempRoot->L[word[i]-'a'];
			tempRoot = tempRoot->child[word[i]-'a'];
		}
	}
}



int main()
{
	int count = 0;
	cin >> count;
	string insertStr;
	for (int i = count; i > 0; i--)
	{
		cin >> insertStr;
		Insert(insertStr);
	}
	cin >> count;
	for (int i = count; i > 0; i--)
	{
		cin >> insertStr;
		cout<