dynamic programming

Edit Distance

Edit Distance (Levenshtein Distance) computes the minimum number of single-character operations (insertions, deletions, and substitutions) required to transform one string into another. A 2D DP table is built where dp[i][j] represents the edit distance between the first i characters of word1 and the first j characters of word2. This is fundamental to many string comparison applications.