word_break_II

hitzzc · hitzzc · commit 36a5a379c7d1 · 2016-10-12T13:19:31.000+08:00
diff --git a/README.md b/README.md
@@ -123,6 +123,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [137. single number II](https://github.com/hitzzc/go-leetcode/tree/master/single_number_II)
 #### [138. copy_list_with_random_pointer](https://github.com/hitzzc/go-leetcode/tree/master/copy_list_with_random_pointer)
 #### [139. word break](https://github.com/hitzzc/go-leetcode/tree/master/word_break)
+#### [140. word break II](https://github.com/hitzzc/go-leetcode/tree/master/word_break II)
 
 
 
diff --git a/word_break_II/word_break_II.cpp b/word_break_II/word_break_II.cpp
@@ -0,0 +1,35 @@
+#include <string>
+#include <unordered_set>
+#include <vector>
+using namespace std;
+
+class Solution {
+public:
+	vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
+		vector<bool> history(s.size()+1, true);
+		vector<string> results;
+		vector<string> path;
+		DFS(s, 0, results, path, history, wordDict);
+		return results;
+	}
+
+	void DFS(string s, int start, vector<string>& results, vector<string>& path, vector<bool>& history, unordered_set<string>& wordDict){
+		if (start==s.size()){
+			if (path.empty()) return;
+			string ret = path[0];
+			for (int i = 1; i < path.size(); ++i)
+				ret = ret + " " + path[i];
+			results.push_back(ret);
+			return;
+		}
+		int pre_num = results.size();
+		for (int end = start+1; end <= s.size(); ++end){
+			if (!history[end] || wordDict.find(s.substr(start, end-start))==wordDict.end()) continue;
+			path.push_back(s.substr(start, end-start));
+			DFS(s, end, results, path, history, wordDict);
+			path.pop_back();
+		}
+		if (results.size()==pre_num) history[start] = false;
+		return;
+	}
+};
