תיאור השאלה
Given two strings s and t, return the number of distinct subsequences of s that are equal to t. A subsequence is formed by deleting some (or no) characters without changing the order of the rest.
איך פותרים?
תכנון דינמי: dp[j] הוא מספר הדרכים ליצור את j התווים הראשונים של t מהתחילית של s שעברנו עליה. לכל תו של s עוברים על t מהסוף להתחלה: אם התווים שווים, מוסיפים ל־dp[j] את dp[j-1]. מספר הדרכים ליצור מחרוזת ריקה הוא 1. סיבוכיות: O(n·m) זמן, O(m) זיכרון.
פתרון קוד
JavaScript
Python
function numDistinct(s, t) {
const dp = new Array(t.length + 1).fill(0);
dp[0] = 1;
for (const ch of s) {
for (let j = t.length; j >= 1; j--) {
if (ch === t[j - 1]) dp[j] += dp[j - 1];
}
}
return dp[t.length];
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.