10000 dp on strings,stocks , · Jashans254/DSA_cpp@3ed8b0e · GitHub
[go: up one dir, main page]
Skip to content

Commit 3ed8b0e

Browse files
author
jashanpreet singh
committed
dp on strings,stocks ,
1 parent f3f4b1e commit 3ed8b0e

17 files changed

+584
-2
lines changed

‎.vscode/tasks.json

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
{
2+
"tasks": [
3+
{
4+
"type": "cppbuild",
5+
"label": "C/C++: gcc.exe build active file",
6+
"command": "C:\\mingw\\mingw32\\bin\\gcc.exe",
7+
"args": [
8+
"-fdiagnostics-color=always",
9+
"-g",
10+
"${file}",
11+
"-o",
12+
"${fileDirname}\\${fileBasenameNoExtension}.exe"
13+
],
14+
"options": {
15+
"cwd": "${fileDirname}"
16+
},
17+
"problemMatcher": [
18+
"$gcc"
19+
],
20+
"group": {
21+
"kind": "build",
22+
"isDefault": true
23+
},
24+
"detail": "Task generated by Debugger."
25+
}
26+
],
27+
"version": "2.0.0"
28+
}

‎DP/lec10_76.cpp

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
class Solution {
2+
public:
3+
4+
int f(int i , int j , string &s , string &t,vector<vector<int>>&dp){
5+
6+
if(i == 0 || j== 0) return 0;
7+
8+
if(dp[i][j]!=-1) return dp[i][j];
9+
if(s[i-1] == t[j-1]) return dp[i][j]= 1 + f(i-1 , j-1 , s , t,dp);
10+
11+
return dp[i][j]=max(f(i-1,j , s , t,dp),f(i , j-1 , s , t,dp));
12+
}
13+
int longestCommonSubsequence(string s, string t) {
14+
15+
int n = s.size();
16+
int m = t.size();
17+
18+
vector<vector<int>>dp( n+1 , vector<int>( m+1 ,-1));
19+
return f(n , m , s , t,dp);
20+
}
21+
};

‎DP/lec10_77.cpp

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
class Solution {
2+
public:
3+
4+
int f(int i , int j , string &s , string &t,vector<vector<int>>&dp){
5+
6+
if(i < 0 || j< 0) return 0;
7+
8+
if(dp[i][j]!=-1) return dp[i][j];
9+
if(s[i] == t[j]) return dp[i][j]= 1 + f(i-1 , j-1 , s , t,dp);
10+
11+
return dp[i][j]=max(f(i-1,j , s , t,dp),f(i , j-1 , s , t,dp));
12+
}
13+
int longestCommonSubsequence(string s, string t) {
14+
15+
int n = s.size();
16+
int m = t.size();
17+
18+
vector<vector<int>>dp( n , vector<int>( m ,-1));
19+
return f(n-1 , m - 1 , s , t,dp);
20+
}
21+
};

‎DP/lec10_78.cpp

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
class Solution {
2+
public:
3+
4+
int longestCommonSubsequence(string s, string t) {
5+
6+
int n = s.size();
7+
int m = t.size();
8+
9+
vector<vector<int>>dp( n+1 , vector<int>( m+1 ,-1));
10+
11+
for(int j = 0 ; j<=m;j++) dp[0][j] = 0;
12+
for(int i = 0 ; i<=n;i++) dp[i][0] = 0 ;
13+
for(int i = 1 ;i<=n;i++){
14+
15+
for(int j = 1 ;j<=m;j++){
16+
if(s[i-1] == t[j-1]) dp[i][j]= 1 + dp[i-1 ][ j-1 ];
17+
else
18+
dp[i][j]=max(dp[i-1][j],dp[i ][ j-1]);
19+
}
20+
}
21+
return dp[n][m];
22+
}
23+
};

‎DP/lec10_79.cpp

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
class Solution {
2+
public:
3+
4+
int longestCommonSubsequence(string s, string t) {
5+
6+
int n = s.size();
7+
int m = t.size();
8+
9+
vector<vector<int>>dp( n+1 , vector<int>( m+1 ,-1));
10+
vector<int> prev(m+1 , 0) , cur(m+1,0);
11+
for(int j = 0 ; j<=m;j++) prev[j] = 0;
12+
13+
for(int i = 1 ;i<=n;i++){
14+
15+
for(int j = 1 ;j<=m;j++){
16+
if(s[i-1] == t[j-1]) cur[j]= 1 + prev[ j-1 ];
17+
else
18+
cur[j]=max(prev[j],cur[ j-1]);
19+
}
20+
prev = cur;
21+
}
22+
return prev[m];
23+
}
24+
};

‎DP/lec10_80.cpp

Lines changed: 125 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,125 @@
1+
//{ Driver Code Starts
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
6+
// } Driver Code Ends
7+
8+
class Solution {
9+
10+
11+
public:
12+
vector<string> all_longest_common_subsequences(string s, string t) {
13+
// Code here
14+
int n = s.size(), m = t.size();
15+
16+
vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); // DP table initialized to 0
17+
18+
// Fill the DP table
19+
for (int i = 1; i <= n; i++) {
20+
for (int j = 1; j <= m; j++) {
21+
if (s[i-1] == t[j-1])
22+
dp[i][j] = 1 + dp[i-1][j-1];
23+
else
24+
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
25+
}
26+
}
27+
int len = dp[n][m]; // Answer is in the last cell
28+
29+
vector<string> ans(len , '$')
30+
31+
32+
int index = len -1;
33+
int i = n , j = m;
34+
while(i>0 && j>0){
35+
36+
if(s[i-1] == t[j-1]){
37+
ans[index] = s[i-1];
38+
index--;
39+
i-- , j--;
40+
}
41+
else if(dp[i-1][j] >dp[i][j-1]){
42+
i--;
43+
}
44+
else j--;
45+
}
46+
47+
48+
return ans;
49+
}
50+
};
51+
52+
//{ Driver Code Starts
53+
#include <bits/stdc++.h>
54+
using namespace std;
55+
56+
57+
// } Driver Code Ends
58+
59+
class Solution {
60+
public:
61+
vector<string> all_longest_common_subsequences(string s1, string s2) {
62+
int n1 = s1.size(), n2 = s2.size();
63+
64+
// Step 1: Create and Fill DP Table in Reverse Order
65+
vector<vector<int>> dp(n1 + 1, vector<int>(n2 + 1, 0));
66+
67+
for (int i = n1 - 1; i >= 0; i--) {
68+
for (int j = n2 - 1; j >= 0; j--) {
69+
if (s1[i] == s2[j])
70+
dp[i][j] = 1 + dp[i + 1][j + 1];
71+
else
72+
dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
73+
}
74+
}
75+
76+
// Step 2: Backtracking with Memoization
77+
unordered_set<string> ans; // Using unordered_set for efficiency
78+
unordered_set<string> visited; // To avoid duplicate recursive calls
79+
80+
function<void(int, int, string)> f = [&](int i, int j, string lcs) {
81+
if (i == n1 || j == n2) {
82+
ans.insert(lcs); // Store the LCS found
83+
return;
84+
}
85+
86+
string key = to_string(i) + "," + to_string(j) + "," + lcs;
87+
if (visited.count(key)) return; // Skip if already visited
88+
visited.insert(key);
89+
90+
if (s1[i] == s2[j]) {
91+
f(i + 1, j + 1, lcs + s1[i]);
92+
} else {
93+
if (dp[i][j] == dp[i][j + 1]) f(i, j + 1, lcs);
94+
if (dp[i][j] == dp[i + 1][j]) f(i + 1, j, lcs);
95+
}
96+
};
97+
98+
f(0, 0, "");
99+
100+
vector<string> result(ans.begin(), ans.end());
101+
sort(result.begin(), result.end()); // Sort once at the end
102+
return result;
103+
}
104+
};
105+
106+
107+
108+
//{ Driver Code Starts.
109+
int main() {
110+
int T;
111+
cin >> T;
112+
while (T--) {
113+
string s, t;
114+
cin >> s >> t;
115+
Solution ob;
116+
vector<string> ans = ob.all_longest_common_subsequences(s, t);
117+
for (auto i : ans)
118+
cout << i << " ";
119+
cout << "\n";
120+
cout << "~" << endl;
121+
}
122+
return 0;
123+
}
124+
125+
// } Driver Code Ends

‎DP/lec10_81.cpp

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
//{ Driver Code Starts
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
6+
// } Driver Code Ends
7+
8+
class Solution {
9+
public:
10+
int longestCommonSubstr(string& s, string& t) {
11+
// your code here
12+
13+
int n = s.size(), m = t.size();
14+
15+
vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); // DP table initialized to 0
16+
17+
// Fill the DP table
18+
int ans = 0 ;
19+
for (int i = 1; i <= n; i++) {
20+
for (int j = 1; j <= m; j++) {
21+
if (s[i-1] == t[j-1]) {
22+
dp[i][j] = 1 + dp[i-1][j-1];
23+
ans = max ( ans ,dp[i][j]);}
24+
else {
25+
dp[i][j] = 0; }
26+
}
27+
}
28+
29+
return ans;
30+
}
31+
};
32+
33+
34+
//{ Driver Code Starts.
35+
36+
int main() {
37+
int t;
38+
cin >> t;
39+
while (t--) {
40+
string s1, s2;
41+
cin >> s1 >> s2;
42+
Solution ob;
43+
44+
cout << ob.longestCommonSubstr(s1, s2) << endl;
45+
46+
cout << "~"
47+
<< "\n";
48+
}
49+
}
50+
51+
// } Driver Code Ends

‎DP/lec10_82.cpp

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
//{ Driver Code Starts
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
6+
// } Driver Code Ends
7+
8+
class Solution {
9+
public:
10+
int longestCommonSubstr(string& s, string& t) {
11+
// your code here
12+
13+
int n = s.size(), m = t.size();
14+
15+
vector<vector<int>> dp(n+1, vector<int>(m+1, 0)); // DP table initialized to 0
16+
17+
vector<int> prev(m+1 ,0) , cur(m+1 ,0);
18+
// Fill the DP table
19+
int ans = 0 ;
20+
for (int i = 1; i <= n; i++) {
21+
for (int j = 1; j <= m; j++) {
22+
if (s[i-1] == t[j-1]) {
23+
cur[j] = 1 + prev[j-1];
24+
ans = max ( ans ,cur[j]);}
25+
else {
26+
cur[j] = 0; }
27+
}
28+
prev = cur;
29+
}
30+
31+
return ans;
32+
}
33+
};
34+
35+
36+
//{ Driver Code Starts.
37+
38+
int main() {
39+
int t;
40+
cin >> t;
41+
while (t--) {
42+
string s1, s2;
43+
cin >> s1 >> s2;
44+
Solution ob;
45+
46+
cout << ob.longestCommonSubstr(s1, s2) << endl;
47+
48+
cout << "~"
49+
<< "\n";
50+
}
51+
}
52+
53+
// } Driver Code Ends

‎DP/lec10_83.cpp

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
class Solution {
2+
public:
3+
int longestCommonSubsequence(string s, string t) {
4+
5+
int n = s.size();
6+
int m = t.size();
7+
8+
vector<vector<int>>dp( n+1 , vector<int>( m+1 ,-1));
9+
10+
for(int j = 0 ; j<=m;j++) dp[0][j] = 0;
11+
for(int i = 0 ; i<=n;i++) dp[i][0] = 0 ;
12+
for(int i = 1 ;i<=n;i++){
13+
14+
for(int j = 1 ;j<=m;j++){
15+
if(s[i-1] == t[j-1]) dp[i][j]= 1 + dp[i-1 ][ j-1 ];
16+
else
17+
dp[i][j]=max(dp[i-1][j],dp[i ][ j-1]);
18+
}
19+
}
20+
return dp[n][m];
21+
}
22+
int longestPalindromeSubseq(string s) {
23+
24+
string t = s;
25+
reverse(t.begin() , t.end());
26+
27+
return longestCommonSubsequence(s ,t);
28+
}
29+
};

0 commit comments

Comments
 (0)
0