Dynamic Programming | Practise 3

In this article we talk about dynamic programming.

Lets look at next question:

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.

(A string S is a subsequence of string T if deleting some number of characters from T (possibly 0, and the characters are chosen anywhere from T) results in the string S.)

Example 1:

1
2
3
4
5
6
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".
The answer provided is the shortest such string that satisfies these properties.

Note:

  1. 1 <= str1.length, str2.length <= 1000
  2. str1 and str2 consist of lowercase English letters.

The problem can be found here.

Problem very tricky and need some investigation. One of solutions could be dynamic programming approach.

You can come up with next statement: longest common subsequence of this two strings will be added to final answer only once. And another left chars must be added by order in which they appear from two strings. So, algorithm will be next:

  1. Find longest common subsequence
  2. Add indexes of chars in longest common subsequence to list
  3. Traverse both strings simultaneously and added each chars from strings to final answer, if char is char from longest common subsequence, then add this char once

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public String shortestCommonSupersequence(String s1, String s2) {
        int n1 = s1.length(), n2 = s2.length();
        int [][] cache = new int [n1 + 1][n2 + 1];
        for (int i = 1; i <= n1; ++i) {
            for (int j = 1; j <= n2; ++j) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    cache[i][j] = cache[i-1][j-1] + 1;
                } else {
                    cache[i][j] = Math.max(cache[i-1][j], cache[i][j-1]);
                }
            }
        }
       
        int r = n1, c = n2;
        List<int[]> lcs = new ArrayList<>();
        while(r >= 1 && c >= 1 && cache[r][c] != 0) {
            if (r > 1 && cache[r-1][c] == cache[r][c]) r--;
            else if (c > 1 && cache[r][c-1] == cache[r][c]) c--;
            else {
                lcs.add(new int [] {r - 1, c - 1});
                r--;
                c--;
            }
        }
        Collections.reverse(lcs);
        int i = 0, j = 0, k = 0, n = lcs.size();
        StringBuilder ans = new StringBuilder();
        while(i < n1 && j < n2 && k < n) {
            boolean d1 = lcs.get(k)[0] == i, d2 = lcs.get(k)[1] == j;
            if (d1 && d2)  {
                ans.append(s1.charAt(i));
                ++k;
                ++i;
                ++j;
            } else if (d1 && !d2) {
                ans.append(s2.charAt(j++));
            } else if (!d1 && d2) {
                ans.append(s1.charAt(i++));
            } else {
                ans.append(s1.charAt(i++));
                ans.append(s2.charAt(j++));
            }
        }
        ans.append(s1.substring(i));
        ans.append(s2.substring(j));
        return ans.toString();
    }
    
}

Notes:

  1. Declare cache array of lonest common subsequence
  2. From line 3 to 13 find the lenths of longest common subsequence
  3. From line 15 to 25 find indexes of chars of longest common subsequence
  4. From line 29 to 44 traverse strings and add chars from to answer following rules from step 3 in algorithm
  5. On lines 45 and 46 add left chars