# Decode Ways

- **Canonical ID**: `decode-ways`
- **Canonical URL**: https://dsacheatsheet.com/problems/decode-ways
- **Difficulty**: medium
- **Patterns**: 1D DP
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/decode-ways/

## 1. Core Invariant / The Trick

At index `i`, zero yields `0` single-digit decodings (`"0"` is invalid standalone). Otherwise inherit `dp[i+1]` (1-digit `1..9`) plus `dp[i+2]` whenever `s[i:i+2]` lies in `10..26`.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Backward pass relies exclusively on the next two DP states (`dp1`, `dp2`), yielding O(N) time and O(1) space.

## 3. Minimal Idiomatic Code

### Python
```python
def numDecodings(s: str) -> int:
    dp1, dp2 = 1, 0
    for i in range(len(s) - 1, -1, -1):
        cur = 0 if s[i] == '0' else dp1
        if i + 1 < len(s) and 10 <= int(s[i:i + 2]) <= 26:
            cur += dp2
        dp1, dp2 = cur, dp1
    return dp1
```

### TypeScript
```typescript
export function numDecodings(s: string): number {
  let dp1 = 1, dp2 = 0;
  for (let i = s.length - 1; i >= 0; i--) {
    let cur = s[i] === '0' ? 0 : dp1;
    if (i + 1 < s.length) {
      const two = (s.charCodeAt(i) - 48) * 10 + (s.charCodeAt(i + 1) - 48);
      if (two >= 10 && two <= 26) cur += dp2;
    }
    [dp1, dp2] = [cur, dp1];
  }
  return dp1;
}
```

### C++
```cpp
int numDecodings(string s) {
    int dp1 = 1, dp2 = 0;
    for (int i = (int)s.size() - 1; i >= 0; --i) {
        int cur = (s[i] == '0') ? 0 : dp1;
        if (i + 1 < (int)s.size()) {
            int two = (s[i]-'0')*10 + (s[i+1]-'0');
            if (two >= 10 && two <= 26) cur += dp2;
        }
        dp2 = dp1; dp1 = cur;
    }
    return dp1;
}
```

### Java
```java
int numDecodings(String s) {
    int dp1 = 1, dp2 = 0;
    for (int i = s.length() - 1; i >= 0; i--) {
        int cur = s.charAt(i) == '0' ? 0 : dp1;
        if (i + 1 < s.length()) {
            int two = (s.charAt(i)-'0')*10 + (s.charAt(i+1)-'0');
            if (two >= 10 && two <= 26) cur += dp2;
        }
        dp2 = dp1; dp1 = cur;
    }
    return dp1;
}
```

### Go
```go
func numDecodings(s string) int {
    dp1, dp2 := 1, 0
    for i := len(s) - 1; i >= 0; i-- {
        cur := 0
        if s[i] != '0' { cur = dp1 }
        if i+1 < len(s) {
            two := int(s[i]-'0')*10 + int(s[i+1]-'0')
            if two >= 10 && two <= 26 { cur += dp2 }
        }
        dp1, dp2 = cur, dp1
    }
    return dp1
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Leading zero `"06"` is invalid, and internal `"100"` produces zero ways (do not advance past `"0"` blindly).
- Writing `10 <= int(s[i:i+2]) <= 26` cleanly prevents `"05"` from matching 2-digit rule.

### Follow-ups
- Decode Ways II introduces wildcard `"*"` characters multiplying single-digit options by `9` and 2-digit options across `11..26`.