0

To transform string 'ca' to 'a', I don't understand why the answer is '1, S' (1, substitution) instead of '1, D' (1, deletion).

Since 'a' == 'a', then shouldn't we use the diagonal cell, which is '1, D' ? The instruction says it himself: "so there are actually no substitutions that need to happen".

I'm confused. Thanks in advance.

link to the video: https://youtu.be/YTO92oVoYwA?t=7m43s

Improve this question

1 Answer 1

Reset to default
0

To go from "ca" to "a", we have three possibilities:

  1. Deletion, resulting in (2, D) based on the "c"->"a" cell
  2. Insertion, resulting in (3, I) based on the "ca"->"" cell
  3. Substitution, resulting in (1, S) based on the "c"->"" cell

Substitution adds no cost as the letter is the same, the others add one.

The letter determines the last operation only, maybe that's where you got confused. To find the best path later, you'll have to follow the track from the lower right cell.

Improve this answer
2
  • Thanks! I may need more clarification, please. So the different steps for the 3 possibilities are: 1. 'ca' -> 'aa' (1S) -> 'a'(1D) = 2D (Deletion) Got it. 2. 'ca' -> 'c' (1D) -> NULL (1D) -> 'a' (1I) = 3I (Insertion) Got it. But then, what happens for the substitution? 3. 'ca' -> 'a' (1D) -> 'a' (0S) = 1S (Substitution) Is that it ?
    – Malintzin
    Commented Jun 6, 2018 at 9:21
  • I don't really understand your question. Each cell stands for a transformation of one sub-string into another, the upper left cell (0,None), our base case, corresponds to ''->''. For 3. first step would be to 'c'->'' (1,D), second step 'ca'->'a' (1,S) (no additional cost as same character)
    – Blauelf
    Commented Jun 6, 2018 at 12:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .