Question

http://www.lintcode.com/en/problem/word-break-iii/
Give a dictionary of words and a sentence with all whitespace removed, return the number of sentences you can form by inserting whitespaces to the sentence so that each word can be found in the dictionary.

Example

Given a String CatMat
Given a dictionary ["Cat", "Mat", "Ca", "tM", "at", "C", "Dog", "og", "Do"]
return 3

we can form 3 sentences, as follows:
CatMat = Cat Mat
CatMat = Ca tM at
CatMat = C at Mat

Answer

RunTime : 288ms

class Solution {
public:
	/*
	* @param s: A string
	* @param dict: A dictionary of words dict
	* @return: A boolean
	*/
	int wordBreak3(string &s, unordered_set<string> &dict) {
		// write your code here
		if (s.length() <= 0)
			return 0;
		bool found = true;
		for (auto c : s) {
			bool in = false;
			for (auto d : dict) {
				if (in)
					break;
				for (auto e : d) {
					if (e == c) {
						in = true;
						break;
					}
				}
			}
			if (!in) {
				found = false;
				break;
			}
		}
		if (!found)
			return 0;
		Trie trie;
		for (auto d : dict)
			trie.insert(d);
		result = 0;
		wordBreakHelp(s, trie, 0);
		return result;
	}
private:
	int result;
	struct TrieNode {
		TrieNode() {
			for (int i = 0; i < 256; i++) {
				next[i] = 0;
			}
			s = 0;
		}
		int s;
		TrieNode* next[256];
	};
	class Trie {
	public:
		Trie() {
			root = new TrieNode();
		}
		inline void deleteHelper(TrieNode* root) {
			if (root) {
				for (int i = 0; i < 256; i++) {
					deleteHelper(root->next[i]);
				}
				delete root;
			}
		}
		~Trie() {
			deleteHelper(root);
			root = 0;
		}
		void insert(string& s) {
			TrieNode* iter = root;
			for (auto c : s) {
				if (iter->next[c] == 0)
					iter->next[c] = new TrieNode();
				iter = iter->next[c];
			}
			iter->s = s.length();
		}
		unordered_set<int> search(string& s, int pos) {
			TrieNode* iter = root;
			unordered_set<int> words;
			for (size_t i = pos; i < s.length(); i++) {
				char c = s[i];
				if (iter->next[c] == 0)
					break;
				if (iter->s > 0) {
					words.insert(iter->s);
				}
				iter = iter->next[c];
			}
			if (iter->s > 0) {
				words.insert(iter->s);
			}
			return words;
		}
	private:
		TrieNode* root;
	};
	inline void wordBreakHelp(string& s, Trie& trie, int pos) {
		unordered_set<int> words = trie.search(s, pos);
		if (words.size() > 0) {
			for (auto word : words) {
				if ((pos + word) == s.length()) {
					result++;
				}
				else {
					wordBreakHelp(s, trie, pos + word);
				}
			}
		}
	}
};