CodeStepByStep

Write a method named editDistance that solves the edit distance, or Levenshtein distance, problem using dynamic programming. Your method 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, list, set, map, etc.) necessary to store the data for your dynamic programming algorithm. You are also allowed to define other "helper" methods 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 methods named indexOf and lastIndexOf, but you should not call them. Similarly, the replace and replaceAll members are forbidden. You should limit yourself to using only the following string members:
  • charAt, compareTo, equals, length, size, substring, trim