תיאור השאלה
Given strings s1, s2 and s3, determine whether s3 is formed by an interleaving of s1 and s2: that is, s3 can be split into the characters of s1 and s2 while keeping the relative order of the characters of each.
איך פותרים?
תכנון דינמי: dp[i][j] אומר אם i התווים הראשונים של s1 ו־j הראשונים של s2 יוצרים את i+j התווים הראשונים של s3. מגיעים לתא או מלמעלה (התו האחרון בא מ־s1) או משמאל (מ־s2). מספיק מערך של שורה אחת. סיבוכיות: O(n·m).
פתרון קוד
JavaScript
Python
function isInterleave(s1, s2, s3) {
const m = s1.length;
const n = s2.length;
if (m + n !== s3.length) return false;
const dp = new Array(n + 1).fill(false);
for (let i = 0; i <= m; i++) {
for (let j = 0; j <= n; j++) {
if (i === 0 && j === 0) {
dp[j] = true;
continue;
}
const fromS1 = i > 0 && dp[j] && s1[i - 1] === s3[i + j - 1];
const fromS2 = j > 0 && dp[j - 1] && s2[j - 1] === s3[i + j - 1];
dp[j] = fromS1 || fromS2;
}
}
return dp[n];
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.