- to do
- 13.10] Decode Ways
- totally ignored the special case...! (think what it is)
- dp[i] stores #ways to decode s[0~i-1]
- group cases together according to logical meaning (e.g. cuz last two digits isn't valid code?)
int numDecodings(string s) {
int n = s.size();
if (n==0 || s[0]=='0') return 0;
vector<int> dp(n+1, 1);
for (int i=2; i<n+1; ++i) {
int currDigit = s[i-1]-'0';
int lastDigit = s[i-2]-'0';
if (!currDigit)
if (lastDigit==0 || lastDigit*10 +0>26) return 0;
else dp[i] = dp[i-2];
else //
dp[i] = lastDigit==0 || lastDigit*10 + currDigit>26? dp[i-1] : dp[i-1]+dp[i-2];
}
return dp[n];
}
- 13.11] Word Break
top-down的备忘录法，这个没怎么做过习惯一下格式；另外substr(starti, count), 老是写成range。。
bool dfs(string& s, unordered_set<string>& wordDict, vector<int>& dp, int index) {
if (dp[index] != -1) return dp[index]==1? true : false;
int restLen = s.size()-index;
for (auto& entry : wordDict) {
if (entry.size() > restLen || entry.compare(s.substr(index, entry.size()))!=0) {
continue;
}
if (dfs(s, wordDict, dp, index+entry.size())) {
dp[index] = 1;
return true;
}
}
dp[index] = 0;
return false;
}
bool wordBreak(string s, unordered_set<string>& wordDict) {
// dp[i] tells if s[i~n-1] is solvable(1; solvable; 0:not)
vector<int> dp(s.size()+1, -1);
dp[s.size()] = 1;
return dfs(s, wordDict, dp, 0);
}
- dp的word break
一遍通过的感觉棒棒哒~~
bool wordBreak(string s, unordered_set<string>& wordDict) {
int n = s.size();
vector<bool> dp(n+1, false);
dp[n] = true;
for (int i=n-1; i>=0; --i) {
string curr = s.substr(i, s.size()-i);
for (auto& entry : wordDict) {
if (entry.size() > curr.size()
|| entry.compare(curr.substr(0, entry.size()))!=0) continue;
if (dp[i+entry.size()]) {
dp[i] = true;
break;
}
}
}
return dp[0];
}
- https://leetcode.com/problems/word-break-ii/
out of memory :(
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
int n = s.size();
if (!n) return vector<string>{};
vector<vector<string>> dp(n, vector<string>{});
// dp[i] stores possible sentences using s[i~n-1]
for (int i=n-1; i>=0; --i) {
string curr = s.substr(i, s.size()-i);
for (auto& entry : wordDict) {
if (entry.size() > curr.size() || entry.compare(s.substr(i, entry.size()))!=0) continue;
if (i+entry.size() == n) dp[i].push_back(entry);
else if (!dp[i+entry.size()].empty()) {
for (auto& restStr: dp[i+entry.size()]) {
dp[i].push_back(entry+" "+restStr);
}
}
}
}
return dp[0];
}
mark 超时。。。dfs为什么。。
vector<string> wordBreak(string s, unordered_set<string>& wordDict) {
int n = s.size();
if (!n) return vector<string>{};
vector<vector<string>> dp(n, vector<string>{});
// dp[i] stores words that are prefixes of s[i~n-1]
for (int i=n-1; i>=0; --i) {
// cout<<i<<" : ";
string curr = s.substr(i, s.size()-i);
for (auto& word : wordDict) {
if (word.size()>curr.size() || word!=curr.substr(0, word.size())) continue;
dp[i].push_back(word);
// cout<<" "<<word;
}
// cout<<endl;
}
vector<string> ret;
dfs(n, 0, dp, "", ret);
return ret;
}
void dfs(int n, int next, vector<vector<string>>& dp, string path, vector<string>& ret) {
if (next>=n) {
ret.push_back(path);
return;
}
for (auto& word: dp[next]) {
string newp = path==""? word : path+" "+word;
dfs(n, next+word.size(), dp, newp, ret);
}
}
