E - Sequence Matching Editorial by en_translator

Let dp[\(i\)][\(j\)] \(=\) the answer for the first \(i\) letters of \(A\) and the first \(j\) letters of \(B\), and use Dynamic Programming.

If \(i = 0\) or \(j = 0\), then dp[\(i\)][\(j\)] is obvious. Let us consider dp[\(i\)][\(j\)] where \(i \neq 0\) and \(j \neq 0\). Since \(A_i\) and \(B_j\) are both the last elements of the sequences, the only choices we can take are either removing at least one of \(A_i\) and \(B_j\), or retain both \(A_i\) and \(B_j\) at the same position in the sequences. Therefore, dp[\(i\)][\(j\)] is the minimum of the following values:

  • dp[\(i - 1\)][\(j\)] \( + 1\) (when removing \(A_i\))
  • dp[\(i\)][\(j - 1\)] \( + 1\) (when removing \(B_j\))
  • dp[\(i - 1\)][\(j - 1\)] + (\(1\) if \(A_i \neq B_j\), otherwise \(0\)) (when retaining \(A_i\) and \(B_j\) at the same position)

last update: