1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
export enum EditOperation {
Insert = "insert",
Delete = "delete",
Edit = "edit",
None = "none",
}
interface Diff {
old: string;
new: string;
}
interface Edit {
operation: EditOperation;
diff: Diff;
}
export const calculateLevenshteinOperations = (
str1: string,
str2: string
): Edit[] => {
const len1 = str1.length;
const len2 = str2.length;
const dp: number[][] = Array.from({ length: len1 + 1 }, () =>
Array(len2 + 1).fill(0)
);
// Initialize DP table
for (let i = 0; i <= len1; i++) dp[i][0] = i;
for (let j = 0; j <= len2; j++) dp[0][j] = j;
// Fill DP table
for (let i = 1; i <= len1; i++) {
for (let j = 1; j <= len2; j++) {
const cost = str1[i - 1] === str2[j - 1] ? 0 : 1;
dp[i][j] = Math.min(
dp[i - 1][j] + 1, // Deletion
dp[i][j - 1] + 1, // Insertion
dp[i - 1][j - 1] + cost // Substitution (Edit)
);
}
}
// Backtrack to find operations
let operations: Edit[] = [];
let i = len1,
j = len2;
while (i > 0 || j > 0) {
if (
i > 0 &&
j > 0 &&
dp[i][j] === dp[i - 1][j - 1] &&
str1[i - 1] === str2[j - 1]
) {
// No operation needed
operations.unshift({
operation: EditOperation.None,
diff: { old: str1[i - 1], new: str2[j - 1] },
});
i--;
j--;
} else if (i > 0 && dp[i][j] === dp[i - 1][j] + 1) {
// Delete operation
operations.unshift({
operation: EditOperation.Delete,
diff: { old: str1[i - 1], new: "" },
});
i--;
} else if (j > 0 && dp[i][j] === dp[i][j - 1] + 1) {
// Insert operation
operations.unshift({
operation: EditOperation.Insert,
diff: { old: "", new: str2[j - 1] },
});
j--;
} else if (i > 0 && j > 0) {
// Edit operation
operations.unshift({
operation: EditOperation.Edit,
diff: { old: str1[i - 1], new: str2[j - 1] },
});
i--;
j--;
}
}
// Simplify consecutive "none" operations into single operations
const simplifiedOperations = operations.reduce<Edit[]>((acc, op) => {
if (
acc.length > 0 &&
op.operation === EditOperation.None &&
acc[acc.length - 1].operation === EditOperation.None
) {
acc[acc.length - 1].diff.old += op.diff.old;
acc[acc.length - 1].diff.new += op.diff.new;
} else {
acc.push(op);
}
return acc;
}, []);
return simplifiedOperations;
};
|
