Timus : 1002. Phone Numbers 題解

把電話號碼轉換成為詞典中可以記憶的的單詞的組合，找到最短的組合。

我這道題應用到的知識點：

1 Trie數據結構

2 map的應用

3 動態規劃法Word Break的知識

4 遞歸剪枝法

思路：

1 建立Trie字典樹，方便查找， 但是字典樹不是使用字符來建立的，而是把字符轉換成數字，建立一個數字字典樹， 然後葉子節點設置一個容器vector裝原單詞。

2 動態規劃建立一個表，記錄可以在字典樹中找到的字符串的前綴子串

3 如果找到整個串都在字典樹中，那麼就可以直接返回這個單詞。如果無法直接找到，那麼就要在表中找到一個前綴子串，然後後面部分在字典樹中查找，看是否找到包含這個子串的單詞，並且要求找到的單詞長度最短。- 這裡可以使用剪枝法提高效率。

原題：http://acm.timus.ru/problem.aspx?space=1&num=1002

作者：靖心 - http://blog.csdn.net/kenden23

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

class PhoneNumber1002_2
{
	static const int SIZE = 10;
	struct Node
	{
		vector words;
		Node *children[SIZE];
		explicit Node () : words()
		{
			for (int i = 0; i < SIZE; i++)
			{
				children[i] = NULL;
			}
		}
	};

	struct Trie
	{
		Node *emRoot;
		int count;
		explicit Trie(int c = 0) : count(c)
		{
			emRoot = new Node;
		}
		~Trie()
		{
			deleteTrie(emRoot);
		}
		void deleteTrie(Node *root)
		{
			if (root)
			{
				for (int i = 0; i < SIZE; i++)
				{
					deleteTrie(root->children[i]);
				}
				delete root;
				root = NULL;
			}
		}
	};

	void insert(Trie *trie, string &keys, string &keyWords)
	{
		int len = (int)keys.size();

		Node *pCrawl = trie->emRoot;
		trie->count++;

		for (int i = 0; i < len; i++)
		{
			int k = keys[i] - '0';
			if (!pCrawl->children[k])
			{
				pCrawl->children[k] = new Node;
			}
			pCrawl = pCrawl->children[k];
		}
		pCrawl->words.push_back(keyWords);
	}

	Node *search(Node *root, string &keys)
	{
		int len = (int)keys.size();

		Node *pCrawl = root;
		for (int i = 0; i < len; i++)
		{
			int k = keys[i] - '0';
			if (!pCrawl->children[k])
			{
				return NULL;//沒走完所有keys
			}
			pCrawl = pCrawl->children[k];
		}
		return pCrawl;
	}

	void searchLeft(Node *leaf, Node *r,	int len, int &prun)
	{
		if (len >= prun) return;

		if (leaf->words.size())
		{
			r = leaf;
			prun = len;
			return;
		}

		for (int i = 0; i < SIZE; i++)
		{
			searchLeft(leaf->children[i], r, len+1, prun);
		}
	}

	void wordsToKey(string &keys, string &keyWords, 
		unordered_map &umCC)
	{
		for (int i = 0; i < (int)keyWords.size(); i++)
		{
			keys.push_back(umCC[keyWords[i]]);
		}
	}

	void charsToMap(const string phdig[], unordered_map &umCC)
	{
		for (int i = 0; i < 10; i++)
		{
			for (int k = 0; k < (int)phdig[i].size(); k++)
			{
				umCC[phdig[i][k]] = i + '0';
			}
		}
	}

	string searchComb(Trie *trie, string &num)
	{
		vector tbl(num.size());
		for (int i = 0; i < (int)num.size(); i++)
		{
			string s = num.substr(0, i+1);
			Node *n = search(trie->emRoot, s);
			if (n && n->words.size())
			{
				tbl[i].append(n->words[0]);
				continue;//這裡錯誤寫成break！！
			}
			for (int j = 1; j <= i; j++)
			{
				if (tbl[j-1].size())
				{
					s = num.substr(j, i-j+1);
					n = search(trie->emRoot, s);
					if (n && n->words.size())
					{
						tbl[i].append(tbl[j-1]);
						tbl[i].append(" ");
						tbl[i].append(n->words[0]);
						break;
					}
				}
			}
		}

		if (tbl.back().size())
		{
			return tbl.back();
		}
		
		string ans;
		for (int i = 0; i < (int)tbl.size() - 1; i++)
		{
			if (tbl[i].size())
			{
				string tmp = tbl[i];
				string keys = num.substr(i+1);
				Node *n = search(trie->emRoot, keys);

				if (!n) continue;

				Node *r = NULL;
				int prun = INT_MAX;
				searchLeft(n, r, 0, prun);

				tmp += r->words[0];

				if (ans.empty() || tmp.size() < ans.size())
				{
					ans = tmp;
				}
			}
		}
		return ans.empty()? "No solution." : ans;
	}

	//測試函數，不使用解題
	void printTrie(Node *n)
	{
		if (n)
		{
			for (int i = 0; i < SIZE; i++)
			{
				printTrie(n->children[i]);	
				for (int j = 0; j < (int)n->words.size(); j++)
				{
					cout<words[j]< umCC;
		charsToMap(phdig, umCC);

		int N;
		
		string num, keys, keyWords;
		while ((cin>>num) && "-1" != num)
		{
			cin>>N;

			Trie trie;
			while (N--)
			{
				cin>>keyWords;				
				wordsToKey(keys, keyWords, umCC);

				insert(&trie, keys, keyWords);

				keys.clear();//別忘記清空
			}

			cout<