forked from cpselvis/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsolution139.cpp
More file actions
93 lines (82 loc) · 1.81 KB
/
solution139.cpp
File metadata and controls
93 lines (82 loc) · 1.81 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
/**
* Word Break
*
* cpselvis([email protected])
* Nov 17th, 2016
*/
#include<iostream>
#include<unordered_set>
#include<memory.h>
using namespace std;
class Solution {
//private:
//unordered_set<string> memorized;
public:
/** Consider two words case, simple case.
bool wordBreak(string s, unordered_set<string>& wordDict) {
for (int i = 0; i < s.size(); i ++)
{
string prefix = s.substr(0, i);
if (wordDict.find(prefix) != wordDict.end())
{
string suffix = s.substr(i);
if (wordDict.find(suffix) != wordDict.end())
{
return true;
}
}
}
return false;
}
**/
/* General solution, use iterative, this method is based on two words case.
bool wordBreak(string s, unordered_set<string> &wordDict)
{
if (wordDict.find(s) != wordDict.end()) return true;
if (memorized.find(s) != memorized.end()) return true;
for (int i = 0; i < s.size(); i ++)
{
string prefix = s.substr(0, i);
if (wordDict.find(prefix) != wordDict.end())
{
string suffix = s.substr(i);
bool sub = wordBreak(suffix, wordDict);
if (sub)
{
memorized.insert(suffix);
return true;
}
}
}
return false;
}
*/
bool wordBreak(string s, unordered_set<string> &wordDict)
{
int size = s.size();
bool dp[size + 1];
memset(dp, 0, sizeof(dp));
dp[0] = true;
for (int i = 1; i <= size; i ++)
{
for (int j = i - 1; j >= 0; j --)
{
if (dp[j] && wordDict.find(s.substr(j, i - j)) != wordDict.end())
{
dp[i] = true;
}
}
}
return dp[size];
}
};
int main(int argc, char **argv)
{
Solution s;
unordered_set<string> wordDict;
wordDict.insert("leet");
wordDict.insert("code");
wordDict.insert("word");
wordDict.insert("problem");
cout << s.wordBreak("leetcodewordproblem", wordDict) << endl;
}