Dynamic Programming

Question 1

(Medium) Shortest Common Supersequence

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If multiple answers exist, you may return any of them.

Input: str1 = “abac”, str2 = “cab” Output: “cabac” Explanation: str1 = “abac” is a subsequence of “cabac” because we can delete the first “c”. str2 = “cab” is a subsequence of “cabac” because we can delete the last “ac”.

Answer 1

Approach:

1. Find the lcs of the two strings and form the dp array.
2. Travel the dp array from the back to form the actual lcs string.
3. Then form the shortest supersequence easily by iterating over the lcs, str1, str2. O(m+n).

https://leetcode.com/submissions/detail/374156076/

Question 2

(Medium) Longest Palindromic Subsequence

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input: “bbbab”

Output: 4

Answer 2

**Recursive:** 
 int[][] dp;
 public int longestPalindromeSubseq(String s) {
 dp = new int[s.length()][s.length()];
 for(int i=0;i\< s.length();i++){
 for(int j=0;j\< s.length();j++){
 dp[i][j]=-1;
 } 
 }
 return lps(s,0,s.length()-1);
 }
 public int lps(String s,int i, int j){ 
 if( dp[i][j]!= -1 ) return dp[i][j];
 if( i \> j )return 0;
 if( i==j )return 1;
 if( s.charAt(i)==s.charAt(j) ) return 2 + lps(s,i+1,j-1);
 int max = Math.max( lps(s,i+1,j), lps(s,i,j-1) );
 dp[i][j]=max;
 return max;
 }

Iterative:

public int longestPalindromeSubseq(String s) {
int[][] dp = new int[s.length()][s.length()];

for (int i = s.length() - 1; i > = 0; i–) {
dp[i][i] = 1;
for (int j = i+1; j < s.length(); j++) {
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = dp[i+1][j-1] + 2;
} else {
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
}
return dp[0][s.length()-1];
}

Question 3

(Medium) Sequence Alignment problem

Given as an input two strings msg & keyword, find the minimum penalty to match these both strings.

There are two ways in which u can match characters,

1. insert a gap & take the penalty of Pgap.
2. consider the characters as mismatch & take the penalty of Pxy.

Examples:

Input : X = CG, Y = CA, p_gap = 3, p_xy = 7

Output : X = CG_, Y = C_A, Total penalty = 6

Input : X = AGGGCT, Y = AGGCA, p_gap = 3, p_xy = 2

Output : X = AGGGCT, Y = A_GGCA, Total penalty = 5

Answer 3

Approach:

Classic String DP problem.

dp[i][j] = if(msg[i] == kw[j]) dp[i-1][j-1]

else

dp[i][j] = min(dp[i-1][j-1]+Pxy, dp[i-1][j]+Pgap, dp[i][j-1]+Pgap)

public int minMismatch(String msg, String kw, int x, int y) {
int dp[][] = new int[msg.length() + kw.length() + 1][msg.length() + kw.length() + 1];
for (int i = 0; i < = msg.length() + kw.length(); i++) {
dp[i][0] = i * x;
dp[0][i] = i * x;
}

for (int i = 1; i < = msg.length(); i++) {
for (int j = 1; j < = kw.length(); j++) {
if (msg.charAt(i - 1) != kw.charAt(j - 1))
dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1] + y, dp[i - 1][j] + x), dp[i][j - 1] + x );
else dp[i][j] = dp[i - 1][j - 1];
}
}
return dp[msg.length()][kw.length()];
}