# String
###### tags: `Study_aboard`
## Basic
### Roman to integer
easy one
```cpp
class Solution {
public:
int romanToInt(string s) {
int res = 0;
unordered_map<char, int> m{{'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}};
for (int i = 0; i < s.size(); ++i) {
int val = m[s[i]];
if (i == s.size() - 1 || m[s[i+1]] <= m[s[i]]) res += val;
else res -= val;
}
return res;
}
};
```
### Integer to roman
Initial: 將特殊數字4,9,40等也加入str中，並由大至小開始做
```cpp
class Solution {
public:
string intToRoman(int num) {
string res = "";
vector<int> val{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
vector<string> str{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};
for (int i = 0; i < val.size(); ++i) {
while (num >= val[i]) {
num -= val[i];
res += str[i];
}
}
return res;
}
};
```
Problem: 當數字很大時可能會出現問題
Sol: 用取商法
ex: 將千位的數字取出來(/1000)後，若為0~3 or 5~8，則將M疊加0~3 or 5~8次。若為，則為CM。 (M不會出現4，因為數字限定<3999)
```cpp
class Solution {
public:
string intToRoman(int num) {
string res = "";
vector<char> roman{'M', 'D', 'C', 'L', 'X', 'V', 'I'};
vector<int> value{1000, 500, 100, 50, 10, 5, 1};
for (int n = 0; n < 7; n += 2) {
int x = num / value[n];
if (x < 4) {
for (int i = 1; i <= x; ++i) res += roman[n];
} else if (x == 4) {
res = res + roman[n] + roman[n - 1];
} else if (x > 4 && x < 9) {
res += roman[n - 1];
for (int i = 6; i <= x; ++i) res += roman[n];
} else if (x == 9) {
res = res + roman[n] + roman[n - 2];
}
num %= value[n];
}
return res;
}
};
```
### Reverse words in a string
Initial: use a stack to reverse it
```cpp
class Solution {
public:
string reverseWords(string s) {
stack<string> Stack;
if(s.length()==1) return s;
string temp;
for(int i=0;i<=s.length();i++){
if(i==s.length() || s[i]==' '){
if(temp=="") continue;
Stack.empty()?Stack.push(temp):Stack.push(temp+" ");
temp="";
}
else{
temp+=s[i];
//if(i==s.length()-1) Stack.empty()?Stack.push(temp):Stack.push(temp+" ");
}
}
string res;
while(!Stack.empty()){
res += Stack.top();
Stack.pop();
}
return res;
}
};
```
Space complexity: $O(n)$
Problem: To reduce space to $O(1)$
Sol: reverse the words one by one and reverse the whole string
Example:
1. the sky is blue
2. eht yks si eulb (reverse the words one by one)
3. blue is the sky (reverse the whole string)
The code is hard to understand:
- i will skip whitespace and find words, then copy the words to j
- j will add space between words and copy the words from i
- l is the pos of the start of the word that need to reverse
Space complexity: $O(1)$
```cpp
class Solution {
public:
// function to reverse any part of string from i to j (just one word or entire string)
void reverseword(string &s, int i, int j){
while(i<j){
char t=s[i];
s[i++]=s[j];
s[j--]=t;
}
}
string reverseWords(string &s) {
int i=0, j=0; // j records the pos of redundant white space
int l=0; // l is the start of redundant white space
int len=s.length();
int wordcount=0; // count how many words are done
while(true){
while(i<len && s[i] == ' ') i++; // skip spaces in front of the word
if(i==len) break;
if(wordcount) s[j++]=' '; // add space between words only wordcount!=0 needs space
l=j;
while(i<len && s[i] != ' ') {s[j]=s[i]; j++; i++;} // move the words to redundant space
reverseword(s,l,j-1); // reverse word in place
wordcount++;
}
s.resize(j); // resize result string
reverseword(s,0,j-1); // reverse whole string
return s;
}
};
```
### One edit distance
Three situations
1. s.len()==t.len() -> change one char
2. s.len()==t.len()+1 -> delete one char
3. s.len()==t.len()-1 -> insert one char
If we swap s with t when t.len is bigger, than we can simplify to two cases, delete and change.
```cpp
class Solution {
public:
bool isOneEditDistance(string s, string t) {
if (s.size() < t.size()) swap(s, t);
int m = s.size(), n = t.size(), diff = m - n;
if (diff >= 2) return false;
else if (diff == 1) { // we swap(s,t) so delete or insert -> delete
for (int i = 0; i < n; ++i) {
if (s[i] != t[i]) {
return s.substr(i + 1) == t.substr(i);
}
}
return true;
} else { // change cnt can only be 1
int cnt = 0;
for (int i = 0; i < m; ++i) {
if (s[i] != t[i]) ++cnt;
}
return cnt == 1;
}
}
};
```
### Rearrange String k Distance apart ==Hard==
```Initial``` 先記錄string裡每個char的個數，從第0位開始排，由個數多(較容易靠近的)的先排。寫一個function用來檢查前k位內的char種類，以避免error。
```Sol```
char個數->map
個數多->max heap
```improvements```
原先檢查k位內是否重複的function被改良，改為每次只選 min(k,len) 個 char，選完之後此 char 先不 push 進 heap 中，而是先push進 temp vector，等到此輪結束之後，再將其push進heap。
為何如此就可以保證k內不會重複?
假設x在兩輪中會在k內，表示第一輪x所在的位置x1，與第二輪位置x2的距離小於k，代表之間有一個char沒有再被push進heap中。然而，heap是依照frequency來選的，代表前方的char's frequency必定>=x's frequency，因此不可能發生。
```cpp
class Solution {
public:
string rearrangeString(string str, int k) {
if (k == 0) return str;
string res;
int len = (int)str.size();
unordered_map<char, int> m; // map
for (auto a : str) ++m[a];
priority_queue<pair<int, char>> q; // heap
for (auto it = m.begin(); it != m.end(); ++it) {
q.push({it->second, it->first});
// map <char, int>
// map->second is int
// map->first is char
}
while (!q.empty()) {
vector<pair<int, int>> v;// temp vector to record char that needed to be push in the heap in next round
int cnt = min(k, len);
for (int i = 0; i < cnt; ++i) {
if (q.empty()) return "";
/*將top pop出來，並將其count-1，若count-1>0，再下一輪中將其push進heap中
* */
auto t = q.top(); q.pop();
res.push_back(t.second);
if (--t.first > 0) v.push_back(t);
--len;
}
for (auto a : v) q.push(a);//push in the heap in next round
}
return res;
}
};
```
### Read N Characters Given Read4 II - Call multiple times
Special question to use an api
Not to difficult
```cpp
// Forward declaration of the read4 API.
int read4(char *buf);
class Solution {
public:
int read(char *buf, int n) {
for(int i=0;i<n;i++){
if(readPos==writePos){
writePos = read4(buff);
readPos = 0;
if(!writePos) return i;
}
buf[i] = buff[readPos++];
}
}
private:
int readPos = 0 ;// the pos that we read from buff
int writePos = 0; // the pos we can get from the string
char buff[4];
};
```
## Anagram
### Valid Anagram
1. 分別對兩個輸入參數跑回圈並且丟進相對應的ARRAY裡面
2. input兩個參數一個分別做紀錄+ +，另一個做紀錄 - -
3. 最後在檢查一次集合裡面是不是有大於0的值
```cpp
class Solution {
public:
bool isAnagram(string s, string t) {
// 長度一定要一樣才有可能配對
if (s.length() != t.length())
return false;
int all[26];
for(int i=0;i<26;i++){
all[i] = 0;
}
for (int i = 0; i < s.length(); i++) {
// 如果都能夠組成相對應的那字母數量應該會是一致的
all[s[i] - 'a']++;
all[t[i] - 'a']--;
}
for (int i : all) {
if (i != 0)
return false;
}
return true;
}
};
```
### Anagram Difference
1. 分別對兩個輸入參數跑回圈並且丟進相對應的ARRAY裡面
2. input兩個參數一個分別做紀錄+ +，另一個做紀錄 - -
3. 分別記錄>0的個數(s1需改變的個數)與<0的個數(s2需改變的個數)
4. 若個數大於字串長度即無法使兩者anagram
5. else: ans = (+個數 + -個數)/2
```cpp
// C++ Program to find minimum number
// of manipulations required to make
// two strings identical
#include <bits/stdc++.h>
using namespace std;
// Counts the no of manipulations
// required
int countManipulations(string s1, string s2)
{
int count = 0;
// store the count of character
int char_count[26];
for (int i = 0; i < 26; i++)
{
char_count[i] = 0;
}
// iterate though the first String
// and update count
for (int i = 0; i < s1.length(); i++)
char_count[s1[i] - 'a']++;
// iterate through the second string
// update char_count.
// if character is not found in
// char_count then increase count
for (int i = 0; i < s2.length(); i++)
{
char_count[s2[i] - 'a']--;
}
for(int i = 0; i < 26; ++i)
{
if(char_count[i] != 0)
{
count+=abs(char_count[i]);
}
}
return count;
}
// Driver code
int main()
{
string s1 = "ddcf";
string s2 = "cedk";
cout<<countManipulations(s1, s2);
}
// This code is contributed by vt_m.
```
### Group anagram
1. first sort the string
2. check whether the map has the string, map is the string position of the res
3. if not : res + one vector
4. add the string to res
```cpp
class Solution {
public:
string shortestPalindrome(string s) {
string r = s;
reverse(r.begin(), r.end());
string t = s + "#" + r;
vector<int> next(t.size(), 0);
int j=0, i=1;
while(i<t.size() && j<t.size()){
if(t[i]==t[j]){
next[i] = j+1;
i++;
j++;
continue;
}
else if(j!=0){
j = next[j-1];
continue;
}
else{
i++;
continue;
}
}
return r.substr(0, s.size() - next.back()) + s;
}
};
```
## Palindrome
### Palindrome Partitioning
problem : slow
solution: dynamic programming to optimize
```cpp
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
if(s.size()==1){
vector<string> temp_res={s};
res.push_back(temp_res);
return res;
}
for(int len=1;len<=s.size();len++){
string temp = s.substr(0,len);
if(ispalindrome(temp)){
vector<string> temp_res={temp};
if(len==s.size()){
res.push_back(temp_res);
continue;
}
for(auto v: partition(s.substr(len))){
temp_res={temp};
for(auto sub_v: v){
temp_res.push_back(sub_v);
}
res.push_back(temp_res);
//v.insert(v.begin(), temp);// insert is slow
//res.push_back(v);
}
}
else continue;
}
return res;
}
bool ispalindrome(string s){
for(int i=0;i<=(s.size()-1)/2;i++){
if(s[i]==s[s.size()-i-1]) continue;
else return false;
}
return true;
}
};
```
```cpp
class Solution {
public:
vector<vector<string>> partition(string s) {
vector<vector<string>> res;
vector<string> out;
helper(s, 0, out, res);
return res;
}
void helper(string s, int start, vector<string>& out, vector<vector<string>>& res) {
if (start == s.size()) { res.push_back(out); return; }
for (int i = start; i < s.size(); ++i) {
if (!isPalindrome(s, start, i)) continue;
out.push_back(s.substr(start, i - start + 1)); // push in the vector
helper(s, i + 1, out, res);// recursively do the rest
out.pop_back();// pop out already push in the res
}
}
bool isPalindrome(string s, int start, int end) {
while (start < end) {
if (s[start] != s[end]) return false;
++start; --end;
}
return true;
}
};
```
DP，詳細說明在 Palindrome substring題目中
```cpp
class Solution {
public:
vector<vector<string>> partition(string s) {
int n = s.size();
vector<vector<string>> res;
vector<string> out;
vector<vector<bool>> dp(n, vector<bool>(n));
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= i; ++j) {
if (s[i] == s[j] && (i - j <= 2 || dp[j + 1][i - 1])) {
dp[j][i] = true;
}
}
}
helper(s, 0, dp, out, res);
return res;
}
void helper(string s, int start, vector<vector<bool>>& dp, vector<string>& out, vector<vector<string>>& res) {
if (start == s.size()) { res.push_back(out); return; }
for (int i = start; i < s.size(); ++i) {
if (!dp[start][i]) continue;
out.push_back(s.substr(start, i - start + 1));
helper(s, i + 1, dp, out, res);
out.pop_back();
}
}
};
```
### Palindrome substring
easy
dp[i][j]: 表string i~j是否為palindrome
dp[i][j] is true if s[i] == s[j] && dp[i + 1][j - 1] is true
```cpp
class Solution {
public:
int countSubstrings(string s) {
int n = s.size(), res = 0;
vector<vector<bool>> dp(n, vector<bool>(n));
for (int i = n - 1; i >= 0; --i) {
for (int j = i; j < n; ++j) {
dp[i][j] = (s[i] == s[j]) && (j - i <= 2 || dp[i + 1][j - 1]);
if (dp[i][j]) ++res;
}
}
return res;
}
};
```
### Implement strStr()
KMP implementation
```cpp
class Solution {
public:
int strStr(string haystack, string needle) {
// KMP table
vector <int> KMP(needle.length(),0);
int i=0, j=1;
while(j<needle.length()){
if(needle[i] == needle[j]){//相等
KMP[j] = i+1;
i++;
j++;
continue;
}
else if(i!=0){//不等且i不為0
i = KMP[i-1];//最困難的部分
continue;
}
else{//不等但i為0
j++;
}
}
// comparison
i=0; j=0;
while(j<needle.length() && i<haystack.length()){
if(needle[j]==haystack[i]){
i++;
j++;
continue;
}
else{
if(j==0){
i++;
continue;
}
else{
j = KMP[j-1];
continue;
}
}
}
if(j==needle.length()){
return i-j;
}
else{
return -1;
}
}
};
```
### Shortest Palindromic Substring ==Hard==
首先將待處理的字符串s翻轉得到t，然後比較原字符串s和翻轉字符串t，從第一個字符開始逐一比較，如果相等，說明s本身就是回文串，不用添加任何字符，直接返回即可；如果不相等，s去掉最後一位，t去掉第一位，繼續比較，以此類推直至有相等，或者循環結束，這樣就能將==兩個字符串在正確的位置拼接起來了==，但這種寫法卻會超時 TLE，無法通過 OJ。
因此，使用KMP來解決
先分析字串組成，若只能從頭開始加字母，則發現字串必由一個==由0起始的回文(包含一個字母)+一串不回文所組成==，簡寫為 P + NP
例如 babad = baba + d
aacecaaa = aacecaa + a
aaacecaa = aaa + cecaa
將字串s與反字串t相接=> P+NP+NP+P (注意:中間需要多加一個符號作為區隔)
若使用KMP，則可在最後一個位置的table上找到P的長度，並將原字串簡掉P留下NP並加到字串前方
```cpp
class Solution {
public:
string shortestPalindrome(string s) {
string r = s;
reverse(r.begin(), r.end());
string t = s + "#" + r;
vector<int> next(t.size(), 0);
for (int i = 1; i < t.size(); ++i) {
int j = next[i - 1];
while (j > 0 && t[i] != t[j]) j = next[j - 1];
next[i] = (j += t[i] == t[j]);
}
return r.substr(0, s.size() - next.back()) + s;
}
};
```
### Longest Palindromic Substring
#### Method 1
選擇一個中心點並向外擴張 (要注意奇偶有不同形式的對稱，所以要做兩次) -> O(N^2)
```cpp
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() < 2) return s;
int n = s.size(), maxLen = 0, start = 0;
for (int i = 0; i < n - 1; ++i) {
searchPalindrome(s, i, i, start, maxLen);
searchPalindrome(s, i, i + 1, start, maxLen);
}
return s.substr(start, maxLen);
}
void searchPalindrome(string s, int left, int right, int& start, int& maxLen) {
while (left >= 0 && right < s.size() && s[left] == s[right]) {
--left; ++right;
}
if (maxLen < right - left - 1) {
start = left + 1;
maxLen = right - left - 1;
}
}
};
```
#### Method 2
觀察noon，nooon 可以發現若我們使用兩個指標 left, right，且right必須跳過重複的字母，odds or even can be done in the same way.
```cpp
class Solution {
public:
string longestPalindrome(string s) {
if (s.size() < 2) return s;
int n = s.size(), maxLen = 0, start = 0;
for (int i = 0; i < n;) {
if (n - i <= maxLen / 2) break;
int left = i, right = i;
while (right < n - 1 && s[right + 1] == s[right]) ++right;
i = right + 1;
while (right < n - 1 && left > 0 && s[right + 1] == s[left - 1]) {
++right; --left;
}
if (maxLen < right - left + 1) {
maxLen = right - left + 1;
start = left;
}
}
return s.substr(start, maxLen);
}
};
```
#### Method 3 DP
此题还可以用动态规划 Dynamic Programming 来解，根 Palindrome Partitioning II 的解法很类似，我们维护一个二维数组 dp，其中 dp[i][j] 表示字符串区间 [i, j] 是否为回文串，当 i = j 时，只有一个字符，肯定是回文串，如果 i = j + 1，说明是相邻字符，此时需要判断 s[i] 是否等于 s[j]，如果i和j不相邻，即 i - j >= 2 时，除了判断 s[i] 和 s[j] 相等之外，dp[i + 1][j - 1] 若为真，就是回文串，通过以上分析，可以写出递推式如下：
```
dp[i][j] = 1
if i=j or
if j=i+1 && s[i]==s[j] or
s[i]=s[j] && dp[i+1][j-1] ==1
```
```cpp
class Solution {
public:
string longestPalindrome(string s) {
if (s.empty()) return "";
int n = s.size(), dp[n][n] = {0}, left = 0, len = 1;
for (int i = 0; i < n; ++i) {
dp[i][i] = 1;
for (int j = 0; j < i; ++j) {
dp[j][i] = (s[i] == s[j] && (i - j < 2 || dp[j + 1][i - 1]));
if (dp[j][i] && len < i - j + 1) {
len = i - j + 1;
left = j;
}
}
}
return s.substr(left, len);
}
};
```
## Substring
### Longest Substring Without Repeating Characters
如果给一个例子中的例子 "abcabcbb"，让你手动找无重复字符的子串，该怎么找。博主会一个字符一个字符的遍历，比如 a，b，c，然后又出现了一个a，那么此时就应该去掉第一次出现的a，然后继续往后，又出现了一个b，则应该去掉一次出现的b，以此类推，最终发现最长的长度为3。
```cpp
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// res = the max substring so far
// left = the start point of the max substring
int res = 0, left = 0, n = s.size();
unordered_map<int, int> m;
for (int i = 0; i < n; ++i) {
if (m.count(s[i]) && m[s[i]] >= left) {
// map.count 即檢查是否有存入值
// m[s[i]] >= left 檢查上一個s[i]是否 in max substring之中
left = m[s[i]] + 1;
}
m[s[i]] = i;
res = max(res, i - left + 1);
}
return res;
}
};
```
### Longest substring with at most K distinct characters
1. map 用來記錄現在的longest string 各有幾個字母
2. map.size() > k時，代表超過k個distinct char
3. 所以從left(substring 的 start) 開始一個一個減直到 map.size() < k
4. 比較 res , i-left+1 的大小
```cpp
class Solution {
public:
int lengthOfLongestSubstringKDistinct(string s, int k) {
int res = 0, left = 0;
unordered_map<char, int> m;
for (int i = 0; i < s.size(); ++i) {
++m[s[i]];
while (m.size() > k) {
if (--m[s[left]] == 0) m.erase(s[left]);
++left;
}
res = max(res, i - left + 1);
}
return res;
}
};
```
### ==Minimum Window Substring==
- 先扫描一遍T，把对应的字符及其出现的次数存到 HashMap 中。
- 然后开始遍历S，就把遍历到的字母对应的 HashMap 中的 value 减一，如果减1后仍大于等于0，cnt 自增1。
- 如果 cnt 等于T串长度时，开始循环，纪录一个字串并更新最小字串值。然后将子窗口的左边界向右移，如果某个移除掉的字母是T串中不可缺少的字母，那么 cnt 自减1，表示此时T串并没有完全匹配。
```cpp
class Solution {
public:
string minWindow(string s, string t) {
string res = "";
unordered_map<char, int> letterCnt;
int left = 0, cnt = 0, minLen = INT_MAX;
// left 左指標
// cnt substring有幾個t的char
// minLen = min len so far
for (char c : t) ++letterCnt[c];
for (int i = 0; i < s.size(); ++i) {
if (--letterCnt[s[i]] >= 0) ++cnt;
while (cnt == t.size()) { // substring已經包含t
if (minLen > i - left + 1) {
minLen = i - left + 1;
res = s.substr(left, minLen);
}
if (++letterCnt[s[left]] > 0) --cnt; // 表left減去了一個t中的char
++left;
}
}
return res;
}
};
```
## Parentheses
### Generate Parentheses
#### Method 1
generate all the string then delete the wrong ones
```cpp
// To generate all possible string
void generateStr(string cur, int n, vector<string>& vsResult)
{
if (n == 0)
{
if (isValid(cur))
{
vsResult.push_back(cur);
}
}
else
{
generateStr(cur+"(", n - 1, vsResult);
generateStr(cur+")", n - 1, vsResult);
}
}
```
#### Method 2
假設我知道有n組()要排列，**而每一組的"("必須要比")"還要先出現**，那我們就可以假設open為還沒放入的"("的數量，close為還沒放入的")"數量：
void generateStr(string combination, int open, int close)
1. Initiale : open一開始就是n，close為0
2. 當每排入一個open，就少一個open要排入，但多一個close排入；當排入一個close，就少一個close可以排入，open的數量不變
3. 最後當open和close都為0的時候，就表示排完了
```cpp
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
addingpar(res, "", n, 0);
return res;
}
void addingpar(vector<string> &v, string str, int open, int close){
if(open==0 && close==0) {
v.push_back(str);
return;
}
if(close > 0){ addingpar(v, str+")", open, close-1); } // 會繼續做下去 因此可以產生多個不同結果
if(open > 0){ addingpar(v, str+"(", open-1, close+1); }
}
};
```
<br><br>
### Longest Valid Parentheses
set a stack, push the position when we met '(', and pop the position from the stack when we met ')'
```cpp
class Solution {
public:
int longestValidParentheses(string s) {
int res = 0, start = 0, n = s.size();
stack<int> st;
for (int i = 0; i < n; ++i) {
if (s[i] == '(') st.push(i);
else if (s[i] == ')') {
if (st.empty()) start = i + 1;
else {
st.pop();
res = st.empty() ? max(res, i - start + 1) : max(res, i - st.top());
// 若pop完st為空，長度即為 i-start+1，去跟res比大小
// 不為空，長度等於 i-stack.top()
}
}
}
return res;
}
};
```
#### 求極值: DP OR GREADY : DP to optimize the memory
1.状态：
DP[i]：以s[i-1]为结尾的longest valid parentheses substring的长度。
2.通项公式：
s[i] = '('：DP[i] = 0
s[i] = ')'：找i前一个字符的最长括号串DP[i]的前一个字符j = i-2-DP[i-1]
DP[i] = DP[i-1] + 2 + DP[j]，如果j >=0，且s[j] = '('
DP[i] = 0，如果j<0，或s[j] = ')'
......... ( x x x x )
j i-2 i-1
证明：不存在j' < j，且s[j' : i]为valid parentheses substring。
假如存在这样的j'，则s[j'+1 : i-1]也valid。那么对于i-1来说：
( x x x x x
j' j'+1 i-1
这种情况下，i-1是不可能有比S[j'+1 : i-1]更长的valid parentheses substring的。
3.计算方向
显然自左向右，且DP[0] = 0
```cpp
class Solution {
public:
int longestValidParentheses(string s) {
int n = s.size(), maxLen = 0;
vector<int> dp(n+1,0);
for(int i=1; i<=n; i++) {
int j = i-2-dp[i-1];
if(s[i-1]=='(' || j<0 || s[j]==')')
dp[i] = 0;
else {
dp[i] = dp[i-1]+2+dp[j];
maxLen = max(maxLen, dp[i]);
}
}
return maxLen;
}
};
```
<br><br>
### Different Ways to Add Parentheses
#### ==Learn Divide and conquer==
1. divide problem into small problem and make sure they can obtain the same rule
2. conqure (recursively sovle the small problem)
3. merge small problem into the final answer
[reference](https://medium.com/brandons-computer-science-notes/divide-and-conquer-algorithms-4e83d9999ffa)
```cpp
class Solution {
public:
vector<int> diffWaysToCompute(string input) {
vector<int> res;
for (int i = 0; i < input.size(); ++i) {
if (input[i] == '+' || input[i] == '-' || input[i] == '*') {
vector<int> left = diffWaysToCompute(input.substr(0, i));
vector<int> right = diffWaysToCompute(input.substr(i + 1));
for (int j = 0; j < left.size(); ++j) {
for (int k = 0; k < right.size(); ++k) {
if (input[i] == '+') res.push_back(left[j] + right[k]);
else if (input[i] == '-') res.push_back(left[j] - right[k]);
else res.push_back(left[j] * right[k]);
}
}
}
}
if (res.empty()) res.push_back(stoi(input)); // input 僅一位數字
return res;
}
};
```
### Remove Invalid Parentheses
這題很出乎意料的是沒有特別的解法，幾乎就是和暴力法一樣，只是中間部分優化可以不用走過每個情形。
暴力法:
每一個 ‘(’ 和 ’)’ 都可以選擇移除或者保留，相當於找到所有的子集 (字母部分不重要)，從裡面中找到合法的以及移除 ‘(’ 或 ’)’ 最少的就是答案了。
找過所有的子集這一部分用遞迴 DFS 就比較簡單了。
(to be continued ...)
Sign in with Wallet
Connect another wallet