word_break

hitzzc · hitzzc · commit 6798e0e28fee · 2016-10-12T11:46:13.000+08:00
diff --git a/README.md b/README.md
@@ -122,6 +122,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
 #### [136. single number](https://github.com/hitzzc/go-leetcode/tree/master/single_number)
 #### [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)
 
 
 
diff --git a/word_break/word_break.cpp b/word_break/word_break.cpp
@@ -0,0 +1,20 @@
+#include <string>
+#include <unordered_set>
+#include <vector>
+using namespace std;
+
+class Solution {
+public:
+	bool wordBreak(string s, unordered_set<string>& wordDict) {
+		vector<bool> history(s.size(), false);
+		for (int i = 0; i < s.size(); ++i){
+			bool yes = false;
+			for (int j = i; j >=0 && !yes; --j){
+				if (wordDict.find(s.substr(j, i-j+1))!=wordDict.end() && (j == 0 || history[j-1]))
+					yes = true;
+			}
+			history[i] = yes;
+		}
+		return history[s.size()-1];
+	}
+};
