getEditDistance

To solve this problem, we will use a dynamic programming approach to build a matrix that represents the edit distance between substrings of the two input strings. We will initialize a matrix with the first row and column representing the distance from an empty string to each character of the two input strings. Then, we will fill in the rest of the matrix by iterating through each character of each string and comparing them to each other.

If the characters are the same, we simply copy the distance value from the previous row and column into the current cell of the matrix. If the characters are different, we can choose to either insert, delete, or substitute a character to make them match. We can then take the minimum of these three options and add 1 to get the new distance.

Once we have filled in the entire matrix, the edit distance between the two strings will be the value in the bottom right cell of the matrix.

Here is the implementation:

function getEditDistance(str1, str2) {
  // Handle edge cases
  if (str1.length === 0) return str2.length;
  if (str2.length === 0) return str1.length;

  // Initialize matrix
  const matrix = [];
  for (let i = 0; i <= str2.length; i++) {
    matrix[i] = [i];
  }
  for (let j = 0; j <= str1.length; j++) {
    matrix[0][j] = j;
  }

  // Fill in matrix
  for (let i = 1; i <= str2.length; i++) {
    for (let j = 1; j <= str1.length; j++) {
      if (str2.charAt(i-1) === str1.charAt(j-1)) {
        matrix[i][j] = matrix[i-1][j-1];
      } else {
        const insert = matrix[i][j-1] + 1;
        const del = matrix[i-1][j] + 1;
        const sub = matrix[i-1][j-1] + 1;
        matrix[i][j] = Math.min(insert, del, sub);
      }
    }
  }

  // Return edit distance
  return matrix[str2.length][str1.length];
}

Big O Complexity Analysis:

The time complexity of the implementation is O(mn), where m and n are the lengths of the input strings. This is because we are filling in an m x n matrix, and each cell requires a constant amount of time to compute.

The space complexity of the implementation is also O(mn), since we are using an m x n matrix to store the edit distances between all possible substrings of the input strings.

Therefore, the time and space complexity of the implementation is proportional to the product of the lengths of the input strings. This is a reasonable complexity for most practical use cases, as it allows us to efficiently compute the edit distance between even very long strings. However, for extremely long strings, the space complexity may become a concern and alternative solutions, such as using a rolling array, may need to be considered.