Edit distance proof when last chars of 2 strings are the same

Question

from Wagner–Fischer_algorithm:

I understand substitution cost needs to be adjusted, either 0 or 1:

 for j from 1 to n:
      for i from 1 to m:
          if s[i] = t[j]:
            substitutionCost := 0
          else:
            substitutionCost := 1

          d[i, j] := minimum(d[i-1, j] + 1,                   // deletion
                             d[i, j-1] + 1,                   // insertion
                             d[i-1, j-1] + substitutionCost)  // substitution

But in later proof part, it claims when s[i] == t[j], d[i, j] = d[i-1, j-1]:

If s[i] = t[j], and we can transform s[1..i-1] to t[1..j-1] in k operations, then we can do the same to s[1..i] and just leave the last character alone, giving k operations.

I don't understand, shouldn't it be d[i, j] = min(d[i-1, j-1], d[i-1, j] + 1, d[i, j-1]+1)?

It's also mentioned in edit distance wiki

How do you prove if the last chars are matched, d[i, j] is d[i-1, j-1]?

---

following the lemma here,

I can think one way to prove this is to assert minimal is not from d[i-1, j-1] when s[i] = t[j]. Then draw contradiction.

if minimal is not from d[i-1, j-1], the minimum must come from

1. deleting last char from s, s[i].
2. or inserting last char from t, t[j].

If we go with 1, we need to match s[0..i-1] with t[0..j].

A: if s[i-1] != t[j],

1. insert t[j] to end of s, we are rewinding to the original state.
2. modify s[i-1] to t[j], it's equvilent to deleting s[i-1] (+1) when matching s[i-1] with t[j-1], whose minimum is d[i-1, j-1].
3. delete s[i-1] -> only viable way

B: if s[i-1] = t[j],

1. no insert t[j], otherwise the previous deletion is redundant.
2. no modification: equivalent to 2nd point in discussion A.
3. deletion -> viable

Combine A and B, only deletion is acceptable and it's impossible to match if only deletion is performed on s.

Do you guys think this proof is correct?

Answer 1

Let's show that if $s$ and $t$ end with the same symbol, then there is always an optimal solution in which the final letters are left alone. Note that there could be other optimal solution in which this is not the case. For example, if $s = a$ and $t = aa$, then an optimal solution would be to delete the final $a$ from $t$. All we are claiming is that some optimal solution leaves these letters alone.

Instead of deleting letters from $s$, let's add them to $t$. The situation thus looks as follows: starting with $s,t$, we add some letters to both, and change some letters in $s$, so that the resulting strings $s',t'$ coincide.

If the final letters in $s',t'$ were both added, then we can improve the solution by not adding them, so we can assume that this is not the case.

If the final letter in $s'$ resulted from changing the last letter in $s$, then necessarily the last letter in $t'$ was added; we can instead not change the last letter in $s$, and add a different letter in $t'$, improving the solution, so we can assume that this is not the case.

Thus either the last letter in $s'$ is that of $s$, or the last letter of $t'$ is that of $t$, or both; in the latter case, there is nothing to prove. The two remaining cases are symmetric, so let's suppose that the last letter in $s'$ is that of $s$, say $\sigma$, while there is a suffix of $t'$, say $r\sigma$ (it must end with $\sigma$!), which was added after the last letter in $t$, which is also $\sigma$.

Instead of adding $r\sigma$ at the very end of $t'$, we add $\sigma r$ just before the final letter of $t$. In both cases this results in an identical suffix $\sigma r \sigma$, so we have converted the given solution to a solution with identical cost in which the final letters of $s,t$ are left untouched.

---

Finally, let me comment that the original paper doesn't seem to make this optimization.