CodeStepByStep

Write a function named editDistance that solves the edit distance, or Levenshtein distance, problem using dynamic programming. Your function accepts string parameters s1 and s2 and returns the "edit distance" between the two strings as an integer. Edit distance (also called Levenshtein distance) is defined as the minimum number of "changes" required to get from s1 to s2 or vice versa. A "change" can be defined as a) inserting a character, b) deleting a character, or c) changing a character to a different character.

The key constraint of this problem is that you must solve it using a bottom-up dynamic programming approach. You are allowed to construct any data structures (array, vector, set, map, etc.) necessary to store the data for your dynamic programming algorithm. You are also allowed to define other "helper" functions if you like. Your solution must also obey the following constraints:

• Do not use recursion. Your solution must use dynamic programming instead.
• Strings have member functions named find and rfind, but you should not call them. Similarly, the replace member is forbidden. You should limit yourself to using only the following string members:
  • at, append, compare, erase, insert, length, size, substr, trim, operators such as [], ==, !=, <, etc.