mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-04 07:29:47 +08:00
86d333ee94
* chore: Switch to Node 20 + Vitest * chore: migrate to vitest mock functions * chore: code style (switch to prettier) * test: re-enable long-running test Seems the switch to Node 20 and Vitest has vastly improved the code's and / or the test's runtime! see #1193 * chore: code style * chore: fix failing tests * Updated Documentation in README.md * Update contribution guidelines to state usage of Prettier * fix: set prettier printWidth back to 80 * chore: apply updated code style automatically * fix: set prettier line endings to lf again * chore: apply updated code style automatically --------- Co-authored-by: github-actions <${GITHUB_ACTOR}@users.noreply.github.com> Co-authored-by: Lars Müller <34514239+appgurueu@users.noreply.github.com>
55 lines
1.3 KiB
JavaScript
55 lines
1.3 KiB
JavaScript
/*
|
|
Wikipedia -> https://en.wikipedia.org/wiki/Edit_distance
|
|
|
|
Q. -> Given two strings `word1` and `word2`. You can perform these operations on any of the string to make both strings similar.
|
|
- Insert
|
|
- Remove
|
|
- Replace
|
|
Find the minimum operation cost required to make both same. Each operation cost is 1.
|
|
|
|
Algorithm details ->
|
|
time complexity - O(n*m)
|
|
space complexity - O(n*m)
|
|
*/
|
|
|
|
const minimumEditDistance = (word1, word2) => {
|
|
const n = word1.length
|
|
const m = word2.length
|
|
const dp = new Array(m + 1).fill(0).map((item) => [])
|
|
|
|
/*
|
|
fill dp matrix with default values -
|
|
- first row is filled considering no elements in word2.
|
|
- first column filled considering no elements in word1.
|
|
*/
|
|
|
|
for (let i = 0; i < n + 1; i++) {
|
|
dp[0][i] = i
|
|
}
|
|
|
|
for (let i = 0; i < m + 1; i++) {
|
|
dp[i][0] = i
|
|
}
|
|
|
|
/*
|
|
indexing is 1 based for dp matrix as we defined some known values at first row and first column/
|
|
*/
|
|
|
|
for (let i = 1; i < m + 1; i++) {
|
|
for (let j = 1; j < n + 1; j++) {
|
|
const letter1 = word1[j - 1]
|
|
const letter2 = word2[i - 1]
|
|
|
|
if (letter1 === letter2) {
|
|
dp[i][j] = dp[i - 1][j - 1]
|
|
} else {
|
|
dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1
|
|
}
|
|
}
|
|
}
|
|
|
|
return dp[m][n]
|
|
}
|
|
|
|
export { minimumEditDistance }
|