תיאור השאלה
Given two strings word1 and word2, return the minimum number of operations needed to convert word1 into word2. The allowed operations are inserting a character, deleting a character, and replacing a character.
איך פותרים?
תכנון דינמי: dp[i][j] הוא המרחק בין i התווים הראשונים של word1 ל־j התווים הראשונים של word2. אם התווים שווים לוקחים את dp[i-1][j-1], אחרת 1 ועוד המינימום בין החלפה, מחיקה והוספה. סיבוכיות: O(n·m).
פתרון קוד
JavaScript
Python
function minDistance(word1, word2) {
const m = word1.length;
const n = word2.length;
const dp = Array.from({ length: m + 1 }, (_, i) =>
Array.from({ length: n + 1 }, (_, j) => (i === 0 ? j : j === 0 ? i : 0))
);
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.