Find the edit distance between the String "ARTIFICIAL" and NATURAL" Using dynamic programming.

The Edit Distance (or Levenshtein Distance) is a string similarity measure. It is the least number of operations (insertions, deletions, or substitutions) to transform one string into another. In this description, we will find the edit distance between the strings "ARTIFICIAL" and "NATURAL" using Dynamic Programming (DP).

Here’s the DP table (cells) representation for computing the Edit Distance between "ARTIFICIAL" and "NATURAL" using Dynamic Programming.

Step 1: Define Strings

• String 1 (s1) = "ARTIFICIAL" (length M = 10)
• String 2 (s2) = "NATURAL" (length N = 7)

Allowed operations:

• Insertion (+1)
• Deletion (+1)
• Substitution (+1 if different)

Step 2: Create DP Table

We construct a (M+1) x (N+1) table, where:

Rows represent characters of "ARTIFICIAL" (plus an empty row for initialization).

Columns represent characters of "NATURAL" (plus an empty column for initialization).

Step 3: Fill the Base Cases

• First row (dp[0][j]): Converting empty "" → "NATURAL" (Insert all characters).
  • dp[0][j] = j
• First column (dp[i][0]): Converting "ARTIFICIAL" → "" (Delete all characters).
  • dp[i][0] = i

Step 4: Compute the DP Table

Each cell dp[i][j] is computed as:

• If s1[i-1] == s2[j-1], copy the diagonal value: $$dp[i][j] = dp[i-1][j-1]$$
• Otherwise, take the minimum of:
  • Insertion: dp[i][j-1] + 1
  • Deletion: dp[i-1][j] + 1
  • Substitution: dp[i-1][j-1] + 1

Now, let's correctly fill the table.

Edit Distance Table

Each cell dp[i][j] represents the minimum number of operations to convert the first i characters of "ARTIFICIAL" to the first j characters of "NATURAL".

Edit Distance between "ARTIFICIAL" and "NATURAL" using Dynamic Programming

Explanation of Cells

Base cases (first row & first column):

Convert empty string to "NATURAL" → cost = column index

Convert "ARTIFICIAL" to empty string → cost = row index

Inner cells:

If characters match (e.g., 'A' in both strings at certain positions), take the diagonal value (no cost).

Otherwise, compute 1 + min(deletion, insertion, replacement).

Final Answer

The bottom-right cell dp[10][7] = 7, meaning "ARTIFICIAL" → "NATURAL" takes 7 operations.

Conclusion

Using Dynamic Programming, we found that the edit distance between "NATURAL" and "ARTIFICIAL" is 7. This process solves the problem efficiently by breaking it down into smaller subproblems and reusing their solutions. The DP table efficiently illustrates the process of change and hence can be used as an efficient instrument for string alignment and comparison problems.