Difficulty: Hard Language: JavaScript
Background and History
The edit distance algorithm is widely used by data scientists and is the basic algorithm used as the evaluation standard for machine translation and speech recognition.
The edit distance of strings, also known as Levenshtein distance, was proposed by Russian mathematician Vladimir Levenshtein in 1965. Refers to the minimum number of operands required to convert a string A into a string B using character operations.
Problem Description
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.
You have the following three operations permitted on a word:
Insert a character
Delete a character
Replace a character
Solution
The smaller the edit distance of two strings, the more similar they are .If two strings are equal, their edit distance is 0.
Set two pointers i and j for word1 and word2 respectively, traverse the two strings respectively, and only perform the following three operations during the traversal process:
Insert a character
Delete a character
Replace a character: skip if the characters of the two string comparisons are the same
matrix[i][j] indicates the edit distance between the word1 starting from the 0th character to the i-th character and the word2 starting from the 0th character to the j-th character.
This solution works great!
Source Code :) https://github.com/codeXXripper/Leetcode-JSLeetcode Problems
Follow me for more