Skip to content

Commit 582496e

Browse files
SeanforfunSeanforfun
committed
[Function add]
1. Add leetcode solutions using C++;
1 parent ec7eead commit 582496e

4 files changed

+227
-1
lines changed

‎leetcode/22. Generate Parentheses.md

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -127,4 +127,24 @@ class Solution {
127127
}
128128
}
129129
}
130+
```
131+
132+
### C++ Version
133+
* Method 1: traceback with restriction
134+
```objectivec
135+
class Solution {
136+
private:
137+
void dfs(int left, int right, string s){
138+
if(left == 0 && right == 0) res_.emplace_back(s);
139+
if(left > 0) dfs(left - 1, right, s + "(");
140+
if(right > left) dfs(left, right - 1, s + ")");
141+
}
142+
vector<string> res_;
143+
public:
144+
vector<string> generateParenthesis(int n) {
145+
if(!n) return res_;
146+
dfs(n, n, "");
147+
return res_;
148+
}
149+
};
130150
```

‎leetcode/301. Remove Invalid Parentheses.md

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -128,5 +128,55 @@ class Solution {
128128
}
129129
```
130130

131+
### C++ Version
132+
* Method 1: dfs
133+
```objectivec
134+
class Solution {
135+
private:
136+
pair<int, int> checkParentheses(string s){
137+
const int n = s.length();
138+
int l = 0, r = 0;
139+
for(int i = 0; i < n; ++i){
140+
if(isalpha(s[i])) continue;
141+
else if(s[i] == '(') l++;
142+
else{
143+
if(l <= 0) r++;
144+
else l--;
145+
}
146+
}
147+
pair<int, int> p(l, r);
148+
return p;
149+
}
150+
vector<string> res_;
151+
bool valid(string s){
152+
int l = 0, r = 0;
153+
for(const char& c : s){
154+
if(c == '(') l++;
155+
else if(c == ')'){
156+
if(++r > l) return false;
157+
}
158+
}
159+
return l == r;
160+
}
161+
void dfs(int l, int r, string s, int index){
162+
if(l == 0 && r == 0 && valid(s)) res_.emplace_back(s);
163+
for(int i = index; i < s.length(); ++i){
164+
if(isalpha(s[i]) || (i > 0 && s[i] == s[i - 1])) continue;
165+
if(r > 0 && s[i] == ')'){
166+
dfs(l, r - 1, s.substr(0, i) + s.substr(i + 1), i);
167+
}else if(l > 0 && s[i] == '('){
168+
dfs(l - 1, r, s.substr(0, i) + s.substr(i + 1), i);
169+
}
170+
}
171+
}
172+
public:
173+
vector<string> removeInvalidParentheses(string s) {
174+
pair<int, int> p = checkParentheses(s);
175+
dfs(p.first, p.second, s, 0);
176+
return res_;
177+
}
178+
};
179+
```
180+
131181
### Reference
132182
1. [花花酱 LeetCode 301. Remove Invalid Parentheses - 刷题找工作 EP139](https://www.youtube.com/watch?v=2k_rS_u6EBk)

‎leetcode/943. Find the Shortest Superstring.md

Lines changed: 110 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -87,7 +87,116 @@ Note:
8787
}
8888
```
8989

90-
* Method 2: DP Need to fill when doing the dp questions.
90+
### C++ Version
91+
* Method 1: brutal force
92+
```objectivec
93+
class Solution {
94+
public:
95+
string shortestSuperstring(vector<string>& A) {
96+
const int n = A.size();
97+
g_ = vector<vector<int>>(n, vector<int>(n));
98+
for(int f = 0; f < n; ++f){
99+
int flen = A[f].length();
100+
for(int s = 0; s < n; ++s){
101+
if(s == f) continue;
102+
int slen = A[s].length();
103+
g_[f][s] = slen;
104+
for(int i = 1; i <= min(flen, slen); ++i){
105+
if(A[f].substr(flen - i) == A[s].substr(0, i))
106+
g_[f][s] = slen - i;
107+
}
108+
}
109+
}
110+
vector<int> path(n);
111+
best_len_ = INT_MAX;
112+
dfs(A, 0, 0, 0, path);
113+
string res = A[path_[0]];
114+
for(int i = 1; i < n; ++i){
115+
int cur_len = A[path_[i]].length();
116+
res += A[path_[i]].substr(cur_len - g_[path_[i - 1]][path_[i]]);
117+
}
118+
return res;
119+
}
120+
private:
121+
vector<vector<int>> g_;
122+
vector<int> path_;
123+
int best_len_;
124+
125+
void dfs(const vector<string>& A, int d, int cur_len, int used, vector<int>& path){
126+
if(cur_len >= best_len_) return;
127+
if(d == A.size()){
128+
best_len_ = cur_len;
129+
path_ = path;
130+
return;
131+
}
132+
for(int i = 0; i < A.size(); ++i){
133+
if(used & (1 << i)) continue;
134+
path[d] = i;
135+
dfs(A,
136+
d + 1,
137+
d == 0 ? A[i].length() : cur_len + g_[path[d - 1]][i],
138+
used | (1 << i),
139+
path);
140+
}
141+
}
142+
};
143+
```
144+
145+
* Method 2: DP
146+
1. dp[s][j]: s is a visited set in binary form, j is the output of current state.
147+
2. Transition function: dp[s][j] = min(dp[s - (1 << j)][i] + g[i][j])
148+
3. initialization: dp[1 << i][i] = A[i].length(), current string's length.
149+
4. final result: min(dp[2^n - 1][*]) with traceback.
150+
```objectivec
151+
class Solution {
152+
public:
153+
string shortestSuperstring(vector<string>& A) {
154+
const int n = A.size();
155+
vector<vector<int>> g(n, vector<int>(n));
156+
for(int f = 0; f < n; ++f){
157+
int flen = A[f].length();
158+
for(int s = 0; s < n; ++s){
159+
if(s == f) continue;
160+
int slen = A[s].length();
161+
g[f][s] = slen;
162+
for(int i = 1; i <= min(flen, slen); ++i){
163+
if(A[f].substr(flen - i) == A[s].substr(0, i))
164+
g[f][s] = slen - i;
165+
}
166+
}
167+
}
168+
vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX >> 1));
169+
vector<vector<int>> parent(1 << n, vector<int>(n, -1));
170+
for(int i = 0; i < n; ++i) dp[1 << i][i] = A[i].length();
171+
for(int s = 1; s < (1 << n); ++s){ // 访问的集合
172+
for(int j = 0; j < n; ++j){ // 最后的出口结点
173+
if(!(s & (1 << j))) continue;
174+
int ps = s & ~(1 << j);
175+
for(int i = 0; i < n; ++i){
176+
if(!(ps & (1 << i))) continue;
177+
if(dp[ps][i] + g[i][j] < dp[s][j]){
178+
dp[s][j] = dp[ps][i] + g[i][j];
179+
parent[s][j] = i;
180+
}
181+
}
182+
}
183+
}
184+
185+
auto it = min_element(begin(dp.back()), end(dp.back()));
186+
int j = it - begin(dp.back());
187+
int s = (1 << n) - 1;
188+
string res;
189+
while(s){
190+
int i = parent[s][j];
191+
if(i < 0) res = A[j] + res;
192+
else res = A[j].substr(A[j].length() - g[i][j]) + res;
193+
s &= ~(1 << j);
194+
j = i;
195+
}
196+
return res;
197+
}
198+
};
199+
```
91200
92201
### Reference
93202
1. [花花酱 LeetCode 943. Find the Shortest Superstring - 刷题找工作 EP231](https://www.youtube.com/watch?v=u_Wc4jwrp3Q)

‎leetcode/996. Number of Squareful Arrays.md

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -174,6 +174,53 @@ Note:
174174
}
175175
```
176176

177+
### C++ version
178+
* Method 1: dp
179+
```objectivec
180+
class Solution {
181+
private:
182+
bool square(int x){
183+
int r = sqrt(x);
184+
return x == r * r;
185+
}
186+
vector<vector<int>> dp_; //dp[cur][state]
187+
188+
int dfs(vector<int>& A, int cur, int to_visit){
189+
if(dp_[cur][to_visit]) return dp_[cur][to_visit];
190+
else if(!to_visit) return 1;
191+
int copy = to_visit;
192+
int pre = -1, index = 0;
193+
while(copy){
194+
if((copy & 1) && square(A[cur] + A[index])){
195+
if(pre == A[index]){
196+
index ++;
197+
copy >>= 1;
198+
continue;
199+
}
200+
pre = A[index];
201+
dp_[cur][to_visit] += dfs(A, index, to_visit ^ (1 << index));
202+
}
203+
index++;
204+
copy >>= 1;
205+
}
206+
return dp_[cur][to_visit];
207+
}
208+
public:
209+
int numSquarefulPerms(vector<int>& A) {
210+
const int n = A.size();
211+
dp_ = vector<vector<int>>(n, vector<int>(1 << n, 0));
212+
sort(A.begin(), A.end());
213+
int res = 0;
214+
int fullstate = (1 << n) - 1;
215+
for(int i = 0; i < n; ++i){
216+
if(i > 0 && A[i] == A[i - 1]) continue;
217+
res += dfs(A, i, fullstate ^ (1 << i));
218+
}
219+
return res;
220+
}
221+
};
222+
```
223+
177224
### Reference
178225
1. [花花酱 LeetCode 996. Number of Squareful Arrays](https://zxi.mytechroad.com/blog/searching/leetcode-996-number-of-squareful-arrays/)
179226

0 commit comments

Comments
 (0)