动态规划-字符串分词

(一)word-break

1
2
3
4
5
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.
For example, given
s ="leetcode",
dict =["leet", "code"].
Return true because"leetcode"can be segmented as"leet code".

动态规划:划分为子问题

  1. dp[j]:表示0-j可分,s[i][j]:表示i,j字符串在dict中
  2. dp[j] = true,当dp[i]&s[i][j]
    1
    2
    3
    4
    5
    6
    7
    8
    bool wordBreak(string s, unordered_set<string> &dict) {
    vector<bool> dp(s.size()+1,false);
    dp[0] = true;
    for(int i = 0;i < s.size();i++)
    for(int j = i+1;dp[i]&&j<=s.size();j++)
    if(dict.find(s.substr(i,j-i))!=dict.end()) dp[j] = true;
    return dp[s.size()];
    }

(二)work-break-ii

1
2
3
4
5
6
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.
For example, given
s ="catsanddog",
dict =["cat", "cats", "and", "sand", "dog"].
A solution is["cats and dog", "cat sand dog"].

动态规划:后面的运算用到前面的结果,把一个问题分解成多个子问题

  1. dp[j]:表示0-j可分,s[i][j]:标识i-j字符串在dict中
  2. dp[j] = dp[i],s[i][j]为真,0<= i < j
  3. 重复2步骤,直到s[0][i]为假且s[0][j]不可分,或s[0][j]为真
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
vector<string> v;
vector<bool> *d;
vector<string> wordBreak(string s, unordered_set<string> &dict) {
d = new vector<bool>[s.length()];
for(int i = 0;i < s.size();i++)
for(int j = 0;j <s.size();j++)
d[i].push_back(false);

for(int i = 0;i<s.size();i++){
for(int j = i;j<s.size();j++){
if( dict.find(s.substr(i,j-i+1)) != dict.end()) d[i][j] = true;
}
}
string t;
wordBreakHelp(s.size()-1,s,t);
return v;
}
void wordBreakHelp(int k,string s,string t){
string t0;
for(int i = k;i>=0;i--){
t0 = t;
if(d[i][k]){
if(i != 0){
t0 = " " + s.substr(i,k-i+1) + t0;
wordBreakHelp(i-1,s,t0);
}
else {
t0 = s.substr(i,k-i+1) + t0;
v.push_back(t0);
}
}
}
}
-------------本文结束感谢您的阅读-------------
鼓励鼓励!