关于Edit Distance递归流程的疑问：为何第二层含eD(2,2)分支

Hey there! Let's unpack this step by step—since you're new to data structures, I'll keep this straightforward with no fancy jargon.

First, let's clarify what eD(i,j) means: it represents the minimum number of operations needed to convert the first i characters of string A into the first j characters of string B. For your case, eD(3,3) is the edit distance between two full 3-character strings.

Why three branches instead of two? #

The three recursive calls directly map to the three fundamental edit operations that define edit distance:

• eD(3,2): This corresponds to an insert operation. Here's the logic: if we insert the 3rd character of string B at the end of string A, we now only need to convert the first 3 characters of A into the first 2 characters of B (since the inserted character already matches B's 3rd). We add 1 to the cost for this insert.
• eD(2,3): This corresponds to a delete operation. If we delete the 3rd character of string A, we now only need to convert the first 2 characters of A into all 3 characters of B. We add 1 to the cost for this delete.
• eD(2,2): This corresponds to a replace operation. Here, we replace the 3rd character of A with the 3rd character of B. If the two characters are identical, this costs 0; if not, it costs 1. After this replacement, we just need to convert the first 2 characters of A into the first 2 characters of B.

Why can't we skip the eD(2,2) branch? #

Skipping the replace operation would mean ignoring a potentially cheaper path. For example:

• Suppose string A is "cat" and string B is "cap". The last characters (t vs p) can be replaced for a cost of 1, plus the edit distance of "ca" to "ca" (which is 0)—total cost 1.
• If we only used delete + insert, we'd delete t (cost 1) then insert p (cost 1), totaling 2—way worse than the replace option.
• If the last characters are identical (e.g., A = "cat", B = "cat"), the replace cost is 0, making eD(2,2) (which is 0) the optimal path with total cost 0.

The recursive approach needs to consider all possible valid operations to find the minimum cost—omitting any branch would lead to incorrect (higher) edit distance values.

内容的提问来源于stack exchange，提问作者Puja Singh