תיאור השאלה
A message of letters is encoded to digits using the mapping 'A' → "1", 'B' → "2", ..., 'Z' → "26". Given a string s of digits, return the number of ways to decode it. A group with a leading zero (like "06") is not valid.
איך פותרים?
תכנון דינמי: מספר הדרכים לפענח עד תו i הוא סכום של שתי אפשרויות. אם הספרה הנוכחית אינה 0 אפשר לפענח אותה לבד, ואם שתי הספרות האחרונות בין 10 ל־26 אפשר לפענח אותן יחד. מספיק לשמור שני ערכים. סיבוכיות: O(n).
פתרון קוד
JavaScript
Python
function numDecodings(s) {
let prev2 = 1; // ways up to i - 2
let prev1 = s[0] === "0" ? 0 : 1; // ways up to i - 1
for (let i = 1; i < s.length; i++) {
let curr = 0;
if (s[i] !== "0") curr += prev1;
const two = Number(s.slice(i - 1, i + 1));
if (two >= 10 && two <= 26) curr += prev2;
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
לעבור את ראיון העבודה הבא שלך בהצלחה
קורס דיגיטלי מקיף עם +25 שיעורים מעשיים, כשעתיים של וידאו, וליווי של מראיין בכיר.