Minimal Editing of Common Subsequence

Question

Given this problem formulation and the official solution in the code block:

Given an array of n integers A and an array of m integers B such that n <= m. What is the minimum number of elements of B that you need to replace by other integers so that A is a subsequence of B? (not necessarily on consecutive indices)

For example, for A = [1, 5, 2, 3] and B = [1, 4, 2, 5, 6, 2, 5], the answer is 1, and it is obtained by replacing the last element of B by 3. Also, for A = [1, 5, 2, 3] and B = [5, 8, 8, 2, 8, 8, 3], the answer is 2, and it is obtained by replacing the first two elements of B by 1 and 5. Your solution needs to run in O(n*m) time.

public static int editToSubsequence(int n, int m, int[] A, int[] B) {
    // IDEA: Dynamic programming DP[i][j] = minimum number of edits such that
    // indices 0...i-1 of A are a subsequence of indices 0...j-1 of B.
    // We set DP[i][j] = n + 1 for j < i, because that case is impossible.
    // Otherwise, the main recursion is:
    //   - if A[i - 1] = B[j - 1], we can set DP[i][j] = DP[i - 1][j - 1]
    //   - else, we can set DP[i][j] = DP[i - 1][j - 1] if we edit B[j],
    //    or DP[i][j] = DP[i][j - 1] if we do not use B[j]
    
    int[][] DP = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j < i; j++) {
        DP[i][j] = n + 1;
      }
    }
    
    for (int i = 1; i <= n; i++) {
      for (int j = i; j <= m; j++) {
        if (A[i - 1] == B[j - 1]) {
          DP[i][j] = DP[i - 1][j - 1];
        } else {
          DP[i][j] = Math.min(DP[i][j - 1], DP[i - 1][j - 1] + 1);
        }
      }
    }
    
    return DP[n][m];
  }

Can someone explain where the intuition for this appraoch should come from? I am familiar with both Longest Common Subsequence and Minimal Edit Distance in DP, but this is not an obvious approach to me.

Do you understand what the DP state represents in the code shown? — Unmitigated
– Unmitigated, Commented Jul 27, 2024 at 23:50
@Unmitigated Not totally clear, especially why we look at A[i-1] and B[j-1] instead of positions i and j, respectively. — CharComplexity
– CharComplexity, Commented Jul 28, 2024 at 0:49
It's because the DP table is using 1-indexing while arrays in Java are 0-indexed. — Unmitigated
– Unmitigated, Commented Jul 28, 2024 at 0:55
The code has a comment at the top that seems to answer your question directly. — Matt Timmermans
– Matt Timmermans, Commented Jul 28, 2024 at 1:21
"the official solution": what does "official" mean in this phrase? — trincot
– trincot, Commented Jul 28, 2024 at 14:59

JackRaBeat · Accepted Answer · 2024-08-07 12:55:02Z

To really understand the Dynamic programming solution I would look on the naive recursive solution first which helps to understand the approach/main idea.

Lets look on the last integer of A and B and the possibilities of the optimal solution.

If the integers are the same, it means the solution of A and B will be the same as A and B without the last integers of both arrays because you can use the last integer in B to be the last integer in A in the subsequence (doesn't matter if you really use it or use another one which can be used).

If they're not the same, you have 2 options:

don't use B last integer at all which means the solution is B without last integer and whole A.
You do use it but you change it which means you again use A and B without last integers of both but plus 1 change cause you must change B last integer to be A last integer.

Now you just need to take the minimal changes between them

About your stopping condition you have also 2 options:

if A length is bigger than B there is no possible solution (will define it as infinite changes)
If A has no integers means you don't need to change anything and B can be any size (will define it as 0 changes)

Now you just need to implement a saving Array which will save the solutions for each (A[i],B[j]) and you got to the DP solution.

Collectives™ on Stack Overflow

Minimal Editing of Common Subsequence

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related