17 July 2023
It was a bit challenging day. I am still learning dynamic programming but as of now I have a good understanding of it and I'll keep on practicing more in the future.
My Solution:
Brute Force
int lcs(string str1, string str2){
if(str1.size()==0 || str2.size()==0){
return 0;
}
if(str1[0]==str2[0]){
return 1+lcs(str1.substr(1), str2.substr(1));
}
else{
int a = lcs(str1.substr(1), str2);
int b = lcs(str1, str2.substr(1));
return max(a,b);
}
}
Memoization
int lcs(string str1, string str2,int** arr){
if(str1.size()==0 || str2.size()==0){
return 0;
}
if(arr[n][m]!=-1){
return arr[n][m];
}
int ans;
if(str1[0]==str2[0]){
ans = 1+lcs(str1.substr(1), str2.substr(1),arr);
}
else{
int a = lcs(str1.substr(1), str2, arr);
int b = lcs(str1, str2.substr(1), arr);
ans = max(a,b);
}
arr[n][m] = ans;
return ans;
}
int getLengthOfLCS(string & str1, string & str2) {
// Write your code here.
int n = str1.size();
int m = str2.size();
int** arr = new int*[n+1];
for(int i=0;i<=n;i++){
arr[i] = new int[m+1];
}
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
arr[i][j] = -1;
}
}
return lcs(str1,str2,arr);}
}
Dynamic Programming
int getLengthOfLCS(string & str1, string & str2) {
// Write your code here.
int n = str1.size();
int m = str2.size();
int** arr = new int*[n+1];
for(int i=0;i<=n;i++){
arr[i] = new int[m+1];
}
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
arr[i][j] = -1;
}
}
for(int i=0;i<=n;i++){
arr[i][0] = 0;
}
for(int j=0;j<=m;j++){
arr[0][j] = 0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(str1[n-i]==str2[m-j]){
arr[i][j] = 1+arr[i-1][j-1];
}
else{
arr[i][j] = max(arr[i-1][j-1],max(arr[i][j-1],arr[i-1][j]));
}
}
}
return arr[n][m];
}
Edit Distance
Given two strings s and t of lengths m and n respectively, find the edit distance between the strings.
Edit Distance
Edit Distance of two strings is minimum number of operations required to make one string equal to other. In order to do so you can perform any of the following three operations only :
1. Delete a character
2. Replace a character with another one
3. Insert a character
Note
Strings don't contain spaces
You need to find the edit distance from input string1 to input string2.
Input Format:
The first line of input contains a string, that denotes the value of s. The following line contains a string, that denotes the value of t.
Output Format:
The first and only line of output contains the count of balanced binary trees modulus 10^9 + 7.
Constraints:
1<= m,n <= 10
Time Limit: 1 second
Sample Input 1:
abc
dc
Sample Output 1:
2
Sample Input 2:
Zeil
trial
Sample Output 2:
3
My solution:
Brute Force
int editDistance(string s, string t) {
// Write your code here
if(s.size()==0 || t.size()==0){
return max(s.size(),t.size());
}
if(s[0]==t[0]){
return editDistance(s.substr(1),t.substr(1));
}
else{
int a = editDistance(s.substr(1),t);
int b = editDistance(s, t.substr(1));
int c = editDistance(s.substr(1), t.substr(1));
return 1+min(a,min(b,c));
}
}
Memoization
int helper(string s,string t,int** arr){
int n = s.size();
int m = t.size();
if(n==0 || m==0){
return max(n,m);
}
if(arr[n][m]!=-1){
return arr[n][m];
}
int ans;
if(s[0]==t[0]){
ans = helper(s.substr(1), t.substr(1), arr);
}
else{
int a = helper(s.substr(1), t, arr);
int b = helper(s, t.substr(1), arr);
int c = helper(s.substr(1), t.substr(1), arr);
ans = 1+min(a,min(b,c));
}
arr[n][m] = ans;
return ans;
}
int editDistance(string s, string t) {
// Write your code here
int n = s.size();
int m = t.size();
int **arr = new int*[n+1];
for(int i=0;i<=n;i++){
arr[i] = new int[m+1];
}
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
arr[i][j] = -1;
}
}
return helper(s,t,arr);
}
Dynamic Programming
int editDistance(string s, string t) {
// Write your code here
int n = s.size();
int m = t.size();
int **arr = new int*[n+1];
for(int i=0;i<=n;i++){
arr[i] = new int[m+1];
}
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){
arr[i][j] = -1;
}
}
arr[0][0] = 0;
for(int i=1;i<=n;i++){
arr[i][0] = i;
}
for(int j=1;j<=m;j++){
arr[0][j] = j;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(s[n-i]==t[m-j]){
arr[i][j] = arr[i-1][j-1];
}
else{
arr[i][j] = 1+ min(arr[i-1][j], min(arr[i-1][j-1], arr[i][j-1]));
}
}
}
return arr[n][m];
}
Knapsack
A thief robbing a store can carry a maximal weight of W into his knapsack. There are N items, and i-th item weigh 'Wi' and the value being 'Vi.' What would be the maximum value V, that the thief can steal?
Input Format:
The first line of the input contains an integer value N, which denotes the total number of items.
The second line of input contains the N number of weights separated by a single space.
The third line of input contains the N number of values separated by a single space.
The fourth line of the input contains an integer value W, which denotes the maximum weight the thief can steal.
Output Format:
Print the maximum value of V that the thief can steal.
Constraints:
1 <= N <= 20
1<= Wi <= 100
1 <= Vi <= 100
Time Limit: 1 sec
Sample Input 1:
4
1 2 4 5
5 4 8 6
5
Sample Output 1:
13
Sample Input 2:
5
12 7 11 8 9
24 13 23 15 16
26
Sample Output 2:
51
My solution:
Brute Force
int knapsack(int* weights, int* values, int n, int maxWeight){
if(n==0){
return 0;
}
int ans1 = INT_MIN;
if(maxWeight-weights[0]>=0){
ans1 = values[0]+knapsack(weights+1,values+1,n-1,maxWeight-weights[0]);
}
int ans2 = knapsack(weights+1,values+1,n-1,maxWeight);
return max(ans1,ans2);
}
Memoization
#include<climits>
int helper(int* weights,int* values, int n,int maxWeight, int** arr, int s){
if(n==0 || maxWeight==0){
return 0;
}
if(arr[maxWeight][s]!=-1){
return arr[maxWeight][s];
}
if(weights[0]>maxWeight){
return helper(weights+1,values+1,n-1,maxWeight,arr,s+1);
}
int ans1 = values[0]+helper(weights+1,values+1,n-1,maxWeight-weights[0],arr,s+1);
int ans2 = helper(weights+1,values+1,n-1,maxWeight,arr,s+1);
arr[maxWeight][s] = max(ans1,ans2);
return max(ans1,ans2);
}
int knapsack(int* weight, int* value, int n, int maxWeight) {
// Write your code here
int** arr[] = new int*[maxWeight+1];
for(int i=0;i<=maxWeight;i++){
arr[i] = new int[n];
}
for(int i=0;i<=maxWeight;i++){
for(int j=0;j<n;j++){
arr[i][j] = -1;
}
}
return helper(weight, value, n, maxWeight, arr, 0);
}
My approach:
I used Hashmap to store characters from the first string but didn't store the duplicate characters in the same string. Also, I used a vector to store those characters which I will use to compare from the second string.
My solution:
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> map;
vector<int> v;
for(int i=0;i<nums1.size();i++){
if(map.count(nums1[i])>0){
continue;
}
map[nums1[i]] = 1;
}
for(int i=0;i<nums2.size();i++){
if(map.count(nums2[i])>0){
if(map[nums2[i]]==1){
map[nums2[i]]++;
v.push_back(nums2[i]);
}
continue;
}
}
return v;
}
};