LCS
Strings
Dynamic Programming
Penelope and her classmates are lost in the Forbidden Forest and the Devil is out to get them. But Penelope has magical powers that can build bridges across the dangerous river and take her friends to safety. The only bridges that can withstand the Devil's wrath are the ones built between two similar trees in the forest. Given str1 and str2 denoting the order of trees on either side of the river, find the maximum number of bridges that Penelope can build and save everyone from the Devil. Note: Each tree in the forest belongs to one of the 3 categories represented by * or # or @.
- Example 1:
str1 = "*@#*"
str2 = "*#"
Output: 2
Explanation: str1 = "*@#*" and str2 = "*#". Two bridges can be built between the banks of the river in the following manner.
* @ # *
| |
* # - Example 2:
str1 = "***"
str2 = "##"
Output: 0
Explanation: No tree of same category can be found between the side of the bank.
➔ Your Task: You don't need to read input or print anything. Complete the function build_bridges() that takes str1 and str2 as input parameters and returns the maximum number of bridges that can be built.
| Expected Time Complexity | Expected Auxiliary Space |
| O(N*M) | O(N*M) |
1 ≤ N , M ≤ 100
Where, N and M are the size of the string str1 and str2 respectively.
- Find longest common subsequence.
public static int build_bridges(String str1 , String str2)
{
return longestCommonSubsequence(str1 , str2);
}
public static int longestCommonSubsequence(String S1, String S2)
{
char[] C1 = S1.toCharArray();
char[] C2 = S2.toCharArray();
int[][] _Dp = new int[C1.length + 1][C2.length + 1];
for (int i=0; i<C1.length; i++)
for (int j=0; j<C2.length; j++)
_Dp[i+1][j+1] = C1[i] == C2[j]? _Dp[i][j]+1 : Math.max(_Dp[i][j+1], _Dp[i+1][j]);
return _Dp[C1.length][C2.length];
}
@author : Shreyansh Kumar Singh ⭐️ GURU-Shreyansh
Problem ID: 706085🖱