Escape The Forbidden Forest Geeks For Geeks
Problem Link:
https://practice.geeksforgeeks.org/problems/a4f19ea532cee502aabec77c07e0d0a45b76ecf9/1#
It is also the problem of the day for 26-02-2022
Solution:
class Sol
{
public static int build_bridges(String s1, String s2)
{
/* tle (Recurisve approach)
if(s1.length()==0|| s2.length()==0){
return 0;
}
else{
StringBuilder sb1=new StringBuilder();
for(int i=0;i<s1.length()-1;i++){
sb1.append(s1.charAt(i));
}
StringBuilder sb2=new StringBuilder();
for(int i=0;i<s2.length()-1;i++){
sb2.append(s2.charAt(i));
}
if(s1.charAt(s1.length()-1)==s2.charAt(s2.length()-1)){
return 1+build_bridges(sb1.toString(),sb2.toString());
}
else{
return Integer.max(build_bridges(sb1.toString(),s2),build_bridges(s1,sb2.toString()));
}
}
*/
(Top-Down Approach)
if(s1.length()==0 || s2.length()==0){
return 0;
}
else{
int t[][]=new int[s1.length()+1][s2.length()+1];
for(int i=0;i<s1.length();i++){
for(int j=0;j<s2.length();j++){
if(i==0 || j==0){
t[i][j]=0;
}
else{
t[i][j]=-1;
}
}
}
for(int i=01;i<s1.length()+1;i++){
for(int j=01;j<s2.length()+1;j++){
if(s1.charAt(i-1)==s2.charAt(j-1)){
t[i][j]=1+t[i-1][j-1];
}
else{
t[i][j]=Integer.max(t[i-1][j],t[i][j-1]);
}
}
}
return t[s1.length()][s2.length()];
}
}
}
TIME COMPLEXITY:O(s1.length()*s2.length())[GFG Time:0.3/1.3]
SPACE COMPLEXITY:O(1)
AUXILIARY SPACE:O(s1.length*s2.length())[Array is used]
APPROACH USED:
Here we are able to make a bridge when characters match ie characters are similar on both sides.
So for that, we need to find out CS(Common subsequence) between two strings.
While in the question they have asked for a maximum number of bridges so for that we need to find out the longest common subsequence(LCS) and that's why every time we take max value(property of Integer.max() function).
We will make one array t of size s1.length()+1 and s2.length()+1
We will start traversing strings from start (Iterative way) and if we found any similar character then we move ahead on both strings and store the value by incrementing with 1 at that particular index.
Otherwise we found outh themaximum between:1
1.(s1-mismatch character) and s2=[t[i-1][j]]
2.(s2-mismatch charater) and s1=[t[i][j-1]]
for example:
s1="abc"
s2 ="ac"
then matrix size will be [3+1][2+1] ie [4][3]
for i==0 or j==0 that is base condition when straings are empty then matric values will be 0.
while for other cases we will see weather character atches or not.
a b c
0 0 0 0 i=0
a 0 i=1
c 0 i=2
j=0 j=1 j=2 j=3
Now starting traversal:
s1="abc" s2="ac"
1) i=1 and j=1:
since 'a' and 'a' matches so s1.charAt(1-1)==s2.charAt(1-1) so t[i][j]=1+t[i-1][j-1]
t[1][1]=1+t[0][0] ===> t[1][1]=1
2)now move to i=1 j=2:
s1.charAt(i-1)!=s2.charAt(j-1) ie 'a'!='b'
t[i][j]=Integer.max(t[i-1][j],t[i][j-1])
t[1][2]=Integer.max(t[0][2],t[1][1]) ===>Integer.max(0,1) ====> 1
Similarly, we will fill the table,
taking values stored in the already traversed cells(subproblems) to fill newly traverse cells and forthcoming too.
a b c
0 0 0 0 i=0
a 0 1 1 1 i=1
c 0 1 1 2 i=2
j=0 j=1 j=2 j=3
The last cell ie t[s1.length()][s2.length()] will give us the final answer as it is the resultant of all subproblems solved earlier and moreoveer in question itself it is asked for common subsequence when strings are s1 and s2 which have size as s1.length() and s2.length(). So we have to return the value with respect to s1.length() and s2.length() ie t[s1.length()][s2.length()].
The time complexity of the top-down approach is less than the recursive approach.
1. In the recursive approach, we use a recursion stack to store the information of calls made while in top-down the result is calculated and stored in matrix immediately making it avoid the usage of O(N*M+1)recursive call stack memory.
2. Also in the top-down approach results of already calculated subproblems are used while in recursion every time we need to call for particular indexes of that particular cell.
TOTAL TEST CASES:200
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment