Find an minimum edit distance between two strings. One edit operation can be insertion, deletion, and substitution at the position from one string to another.
Ideas to solve
1. What is the smallest subproblem?
2. How many variables involved in subproblems?
Cautions:
1. Be careful when dealing with edge cases, and not getting index out of bound error.
Every dynamic programming problems has an directed acyclic graphs, and each node represents a subproblem.
No comments:
Post a Comment