Question

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

Example

Gieve s = lintcode,
dict = ["de", "ding", "co", "code", "lint"].

A solution is ["lint code", "lint co de"].

Answer

RunTime : 902ms

class Solution {
public:
	/*
	* @param s: A string
	* @param dict: A dictionary of words dict
	* @return: A boolean
	*/
	vector<string> wordBreak(string &s, unordered_set<string> &dict) {
		// write your code here
		result.clear();
		if (s.length() <= 0)
			return result;
		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 result;
		Trie trie;
		for (auto d : dict)
			trie.insert(d);
		string bw;
		wordBreakHelp(s, trie, 0, bw);
		return result;
	}
private:
	vector<string> result;
	struct TrieNode {
		TrieNode() {
			for (int i = 0; i < 26; i++) {
				next[i] = 0;
			}
			s = 0;
		}
		int s;
		TrieNode* next[26];
	};
	class Trie {
	public:
		Trie() {
			root = new TrieNode();
		}
		inline void deleteHelper(TrieNode* root) {
			if (root) {
				for (int i = 0; i < 26; 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 - 'a'] == 0)
					iter->next[c - 'a'] = new TrieNode();
				iter = iter->next[c - 'a'];
			}
			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 - 'a'] == 0)
					break;
				if (iter->s > 0) {
					words.insert(iter->s);
				}
				iter = iter->next[c - 'a'];
			}
			if (iter->s > 0) {
				words.insert(iter->s);
			}
			return words;
		}
	private:
		TrieNode* root;
	};
	inline void wordBreakHelp(string& s, Trie& trie, int pos, string& bw) {
		unordered_set<int> words = trie.search(s, pos);
		if (words.size() > 0) {
			for (auto word : words) {
				string bwd = bw;
				if (bwd.empty())
					bwd = s.substr(pos, word);
				else {
					bwd.append(" ");
					bwd.append(s.substr(pos, word));
				}
				if ((pos + word) == s.length()) {
					result.push_back(bwd);
				}
				else {
					wordBreakHelp(s, trie, pos + word, bwd);
				}
			}
		}
	}
};