139. 单词拆分 - medium

用动态规划
第一个版本是没有经过优化的，一开始是用回溯发现超时了，之后用动规优化勉强及格
大概的思路是：

1. 若想要以s[i]结尾的字符串可以被拆分，则以s[k]结尾的字符串，以及string(s, k, i-k)的字符串均可以被拆分即可

//14.07
//14.40
class Solution {unordered_set<string> dict;vector<vector<int>> dp;bool helper(string &str, int start, int end) {if(start >= end) return 0;if(dp[start][end] != -1) return dp[start][end];auto it = dict.find(string(str, start, end-start));//cout << string(str, start, end-start) << ' ';if(it != dict.end()) {dp[start][end] = 1; return 1;}//if(start == end) return 0;//cout << start << ' ' << end-1 << endl;for(int i = start+1; i < end; i++) {int flag = 0;if(helper(str, start, i)) {if(helper(str, i, end))flag = 1;}if(flag) {dp[start][end] = 1; return 1;}}dp[start][end] = 0;return 0;}
public:bool wordBreak(string s, vector<string>& wordDict) {if(s.empty()) return 0;for(auto x : wordDict) {dict.insert(x);}dp.resize(s.size()+1, vector<int> (s.size()+1, -1));return helper(s, 0, s.size());}
};

改良后版本，参考 powcai

class Solution {
public:bool wordBreak(string s, vector<string>& wordDict) {if(s.empty()) return 1;if(wordDict.empty()) return 0;vector<int> dp(s.size()+1, 0);unordered_set<string> bank;for(auto x : wordDict) bank.insert(x);dp[0] = 1;for(int i = 1; i < dp.size(); i++) {for(int k = i-1; k >= 0; k--) {if(dp[k]) {auto it = bank.find(string(s, k, i-k));if(it != bank.end()) {dp[i] = 1;break;}}}}return dp.back();}
};

394. 字符串解码 - medium

很明显要用栈来实现，但第一个版本还是可以被优化的，优化后的第二个版本速度提高了不少

//18.00
//18.24
class Solution {
public:string decodeString(string s) {string res;if(s.empty()) return res;stack<char> tmp;for(int i = 0; i < s.size(); i++) {//cout << i << endl;if(s[i] != ']') {tmp.push(s[i]);}else {string str1, str2;while(tmp.top() != '[') {str1 = tmp.top()+str1;tmp.pop();}tmp.pop();int digit = 0;for(int k = 1; !tmp.empty() && tmp.top() <= '9' && tmp.top() >= '0'; k *= 10) {cout << k << endl;digit += k*(tmp.top()-'0');tmp.pop();}cout << 253 << endl;for(int k = 0; k < digit; k++) str2 = str2+str1;for(auto x : str2) tmp.push(x);}}while(!tmp.empty()) {res = tmp.top()+res;tmp.pop();}return res;}
};

第二种方法这里，需要用到两个stack（这里用vector代替），一个是装times的，另外一个时装str的

class Solution {
public:string decodeString(string s) {if(s.empty()) return "";string res;vector<string> str;vector<int> num;int times = 0;for(auto x : s) {if(x <= '9' && x >= '0') {times = (times*10)+x-'0';}else if((x <= 'z' && x >= 'a') || (x <= 'Z' && x >= 'A')) {res = res+x;}else if(x == '[') {num.push_back(times);times = 0;str.push_back(res);res = "";}else if(x == ']') {times = num.back();num.pop_back();for(int i = 0; i < times; i++) str[str.size()-1] = str.back()+res;res = str.back(); str.pop_back();times = 0;}}return res;}
};