Decode Ways

Medium Dynamic Programming

Count how many ways a digit string can be decoded into letters, where A=1 ... Z=26. Bottom-up DP.

Sample input

226

Sample output

Solution

def num_decodings(s):
    if not s or s[0] == "0":
        return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1
    for i in range(2, n + 1):
        if s[i - 1] != "0":
            dp[i] += dp[i - 1]
        two = int(s[i - 2:i])
        if 10 <= two <= 26:
            dp[i] += dp[i - 2]
    return dp[n]

print(num_decodings("226"))

function numDecodings(s) {
  if (s.length === 0 || s[0] === "0") return 0;
  const n = s.length;
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    if (s[i - 1] !== "0") dp[i] += dp[i - 1];
    const two = parseInt(s.slice(i - 2, i), 10);
    if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
  }
  return dp[n];
}

console.log(numDecodings("226"));

public class Main {
    static int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];
            int two = Integer.parseInt(s.substring(i - 2, i));
            if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
        }
        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(numDecodings("226"));
    }
}

fun numDecodings(s: String): Int {
    if (s.isEmpty() || s[0] == '0') return 0
    val n = s.length
    val dp = IntArray(n + 1)
    dp[0] = 1
    dp[1] = 1
    for (i in 2..n) {
        if (s[i - 1] != '0') dp[i] += dp[i - 1]
        val two = s.substring(i - 2, i).toInt()
        if (two in 10..26) dp[i] += dp[i - 2]
    }
    return dp[n]
}

fun main() {
    println(numDecodings("226"))
}

func numDecodings(_ s: String) -> Int {
    let chars = Array(s)
    if chars.isEmpty || chars[0] == "0" { return 0 }
    let n = chars.count
    var dp = [Int](repeating: 0, count: n + 1)
    dp[0] = 1
    dp[1] = 1
    if n >= 2 {
        for i in 2...n {
            if chars[i - 1] != "0" { dp[i] += dp[i - 1] }
            let two = Int(String(chars[(i - 2)..<i]))!
            if two >= 10 && two <= 26 { dp[i] += dp[i - 2] }
        }
    }
    return dp[n]
}

print(numDecodings("226"))

int numDecodings(String s) {
  if (s.isEmpty || s[0] == '0') return 0;
  final n = s.length;
  final dp = List.filled(n + 1, 0);
  dp[0] = 1;
  dp[1] = 1;
  for (var i = 2; i <= n; i++) {
    if (s[i - 1] != '0') dp[i] += dp[i - 1];
    final two = int.parse(s.substring(i - 2, i));
    if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
  }
  return dp[n];
}

void main() {
  print(numDecodings("226"));
}

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int numDecodings(const string& s) {
    if (s.empty() || s[0] == '0') return 0;
    int n = s.size();
    vector<int> dp(n + 1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (s[i - 1] != '0') dp[i] += dp[i - 1];
        int two = stoi(s.substr(i - 2, 2));
        if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
    }
    return dp[n];
}

int main() {
    cout << numDecodings("226") << endl;
    return 0;
}

#include <stdio.h>
#include <string.h>

int numDecodings(const char *s) {
    int n = strlen(s);
    if (n == 0 || s[0] == '0') return 0;
    int dp[100] = {0};
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (s[i - 1] != '0') dp[i] += dp[i - 1];
        int two = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
        if (two >= 10 && two <= 26) dp[i] += dp[i - 2];
    }
    return dp[n];
}

int main() {
    printf("%d\n", numDecodings("226"));
    return 0;
}