Untitled

Pasted by Anonymous on Sat Nov 7 23:47:09 2026 UTC as Rendered markdown

Decode Ways DP (Practice 5009): Notes

Interviewers use this pattern to test whether you can state the invariant before coding. Here is a compact rehearsal note.

Approach

dp[i] adds dp[i-1] for a valid single digit and dp[i-2] for a valid two-digit code 10..26.

def num_decodings(s):
    a,b=1,0 if s[0]=='0' else 1
    for i in range(1,len(s)):
        c=0
        if s[i]!='0': c+=b
        if 10<=int(s[i-1:i+1])<=26: c+=a
        a,b=b,c
    return b

Complexity

Linear in the dominant input size for the scan; heap/tree variants add a log factor.

Interview pitfalls

State the invariant out loud, name the complexity, then code. Skipping the invariant is the usual fail mode.

Practicing out loud

Narrate the approach, complexity and one edge case in under a minute. Disclosure: I work on Linkjob AI, a real-time interview assistant. If you want live practice help, see www.linkjob.ai.