Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Second - Dynamic Programming (Levenshtein Distance) solution in Clear category for Fuzzy String Matching by freeman_lex
import assert from "assert";
function fuzzyStringMatch(str1: string, str2: string, threshold: number): boolean {
const dp: number[][] = Array(str1.length + 1).fill(0).map(() => Array(str2.length + 1).fill(0));
for (let i = 0; i <= str1.length; i++) {
for (let j = 0; j <= str2.length; j++) {
if (i === 0) {
dp[i][j] = j;
} else if (j === 0) {
dp[i][j] = i;
} else if (str1[i - 1] === str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]);
}
}
}
return dp[str1.length][str2.length] <= threshold;
}
console.log("Example:");
console.log(fuzzyStringMatch("apple", "appel", 2));
// These "asserts" are used for self-checking
assert.strictEqual(fuzzyStringMatch("apple", "appel", 2), true);
assert.strictEqual(fuzzyStringMatch("apple", "bpple", 1), true);
assert.strictEqual(fuzzyStringMatch("apple", "bpple", 0), false);
assert.strictEqual(fuzzyStringMatch("apple", "apples", 1), true);
assert.strictEqual(fuzzyStringMatch("apple", "bpples", 2), true);
assert.strictEqual(fuzzyStringMatch("apple", "apxle", 1), true);
assert.strictEqual(fuzzyStringMatch("apple", "pxxli", 3), false);
console.log("Coding complete? Click 'Check Solution' to earn rewards!");
Sept. 1, 2023
