Decode Ways

                                            
class Solution {
public:
    int numDecodings(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 twoDigit = stoi(s.substr(i - 2, 2));
            if (twoDigit >= 10 && twoDigit <= 26) {
                dp[i] += dp[i - 2];
            }
        }
        
        return dp[n];
    }
};

                                            
class Solution {
    public int numDecodings(String s) {
        if (s == null || s.length() == 0 || 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++) {
            int oneDigit = Integer.parseInt(s.substring(i-1, i));
            int twoDigits = Integer.parseInt(s.substring(i-2, i));
            
            if (oneDigit >= 1) {
                dp[i] += dp[i-1];
            }
            
            if (twoDigits >= 10 && twoDigits <= 26) {
                dp[i] += dp[i-2];
            }
        }
        
        return dp[n];
    }
}

                                            
class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s or s[0] == "0":
            return 0
        
        n = len(s)
        dp = [0] * (n + 1)
        dp[0], dp[1] = 1, 1
        
        for i in range(2, n + 1):
            if s[i - 1] != "0":
                dp[i] += dp[i - 1]
            
            if s[i - 2] == "1" or (s[i - 2] == "2" and s[i - 1] <= "6"):
                dp[i] += dp[i - 2]
        
        return dp[n]

                                            
public class Solution {
    public int NumDecodings(string s) {
        if (string.IsNullOrEmpty(s) || s[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++) {
            int first = int.Parse(s.Substring(i - 1, 1));
            int second = int.Parse(s.Substring(i - 2, 2));

            if (first >= 1 && first <= 9) {
                dp[i] += dp[i - 1];
            }

            if (second >= 10 && second <= 26) {
                dp[i] += dp[i - 2];
            }
        }

        return dp[n];
    }
}

                                            
/**
 * @param {string} s
 * @return {number}
 */
const numDecodings = (s) => {
    const n = s.length;
    let dp = new Array(n + 1).fill(0);
    
    dp[0] = 1;
    dp[1] = s[0] !== '0' ? 1 : 0;
    
    for (let i = 2; i <= n; i++) {
        const oneDigit = parseInt(s.substring(i - 1, i));
        const twoDigits = parseInt(s.substring(i - 2, i));
        
        if (oneDigit >= 1) {
            dp[i] += dp[i - 1];
        }
        
        if (twoDigits >= 10 && twoDigits <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    
    return dp[n];
};

                                            
function numDecodings(s: string): number {
    if (s.length === 0 || s[0] === "0") {
        return 0;
    }
    
    let dp = new Array(s.length + 1).fill(0);
    dp[0] = 1;
    dp[1] = 1;
    
    for (let i = 2; i <= s.length; i++) {
        if (s[i - 1] !== "0") {
            dp[i] += dp[i - 1];
        }
        
        let twoDigit = Number(s.substring(i - 2, i));
        if (twoDigit >= 10 && twoDigit <= 26) {
            dp[i] += dp[i - 2];
        }
    }
    
    return dp[s.length];
};

                                            
class Solution {
    /**
     * @param String $s
     */
    function numDecodings($s) {
        $n = strlen($s);
        $dp = array_fill(0, $n + 1, 0);
        $dp[0] = 1;
        
        $dp[1] = $s[0] == '0' ? 0 : 1;
        
        for ($i = 2; $i <= $n; $i++) {
            $oneDigit = intval(substr($s, $i - 1, 1));
            $twoDigits = intval(substr($s, $i - 2, 2));
            
            if ($oneDigit >= 1) {
                $dp[$i] += $dp[$i - 1];
            }
            
            if ($twoDigits >= 10 && $twoDigits <= 26) {
                $dp[$i] += $dp[$i - 2];
            }
        }
        
        return $dp[$n];
    }
}

                                            
class Solution {
    func numDecodings(_ s: String) -> Int {
        if s.isEmpty || s.first == "0" {
            return 0
        }
        
        let n = s.count
        var dp = [Int](repeating: 0, count: n + 1)
        dp[0] = 1
        dp[1] = 1
        
        for i in 2...n {
            let firstDigit = Int(String(s[s.index(s.startIndex, offsetBy: i - 1)])) ?? 0
            let twoDigits = Int(s[s.index(s.startIndex, offsetBy: i - 2)...s.index(s.startIndex, offsetBy: i - 1)]) ?? 0
            
            if firstDigit > 0 {
                dp[i] += dp[i - 1]
            }
            
            if twoDigits >= 10 && twoDigits <= 26 {
                dp[i] += dp[i - 2]
            }
        }
        
        return dp[n]
    }
}

                                            
class Solution {
    fun numDecodings(s: String): Int {
        if (s.isEmpty() || s[0] == '0') return 0
        if (s.length == 1) return 1

        var dp = IntArray(s.length + 1)
        dp[0] = 1
        dp[1] = if (s[1] == '0') 0 else 1

        for (i in 2..s.length) {
            val oneDigit = s.substring(i - 1, i).toInt()
            val twoDigits = s.substring(i - 2, i).toInt()

            if (oneDigit in 1..9) {
                dp[i] += dp[i - 1]
            }
            if (twoDigits in 10..26) {
                dp[i] += dp[i - 2]
            }
        }

        return dp[s.length]
    }
}

                                            
class Solution {
  int numDecodings(String s) {
    if (s.isEmpty) return 0;
    
    int n = s.length;
    List<int> dp = List.filled(n + 1, 0);
    dp[0] = 1;
    dp[1] = s[0] == '0' ? 0 : 1;
    
    for (int i = 2; i <= n; i++) {
      int oneDigit = int.parse(s.substring(i - 1, i));
      int twoDigits = int.parse(s.substring(i - 2, i));
      
      if (oneDigit >= 1) {
        dp[i] += dp[i - 1];
      }
      
      if (twoDigits >= 10 && twoDigits <= 26) {
        dp[i] += dp[i - 2];
      }
    }
    
    return dp[n];
  }
}

                                            
func numDecodings(s string) int {
    if s[0] == '0' {
        return 0
    }
    
    n := len(s)
    dp := make([]int, n+1)
    dp[0], dp[1] = 1, 1
    
    for i := 2; i <= n; i++ {
        if s[i-1] != '0' {
            dp[i] += dp[i-1]
        }
        if s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <= '6') {
            dp[i] += dp[i-2]
        }
    }
    
    return dp[n]
}

                                            
# @param {String} s
# @return {Integer}
def num_decodings(s)
    return 0 if s.empty? || s[0] == "0"
    
    n = s.length
    dp = Array.new(n+1, 0)
    dp[0] = 1
    dp[1] = 1
    
    (2..n).each do |i|
        one_digit = s[i-1].to_i
        two_digits = s[i-2..i-1].to_i
        
        dp[i] += dp[i-1] if one_digit >= 1 && one_digit <= 9
        dp[i] += dp[i-2] if two_digits >= 10 && two_digits <= 26
    end
    
    return dp[n]
end

                                            
object Solution {
    def numDecodings(s: String): Int = {
        if (s.isEmpty()) return 0

        val n = s.length
        val dp = new Array[Int](n + 1)
        dp(0) = 1
        dp(1) = if (s(0) != '0') 1 else 0

        for (i <- 2 to n) {
            val first = s.substring(i - 1, i).toInt
            val second = s.substring(i - 2, i).toInt

            if (first >= 1 && first <= 9) {
                dp(i) += dp(i - 1)
            }

            if (second >= 10 && second <= 26) {
                dp(i) += dp(i - 2)
            }
        }

        dp(n)
    }
}

                                            
impl Solution {
    pub fn num_decodings(s: String) -> i32 {
        let s = s.as_bytes();
        let n = s.len();
        if n == 0 || s[0] == b'0' {
            return 0;
        }

        let mut dp = vec![0; n + 1];
        dp[0] = 1;
        dp[1] = 1;
        
        for i in 2..=n {
            if s[i-1] != b'0' {
                dp[i] += dp[i-1];
            }
            if s[i-2] == b'1' || (s[i-2] == b'2' && s[i-1] <= b'6') {
                dp[i] += dp[i-2];
            }
        }
        
        dp[n]
    }
}

Explanation

To solve this coding challenge, we need to determine how many ways we can decode a string of digits based on the given encoding rules. Specifically, each digit or pair of digits maps to an alphabet character where 'A' corresponds to "1", 'B' to "2", and so on up to 'Z' mapping to "26". Given an encoded string

s

, the task is to calculate the total number of possible decode ways that the entire string can be interpreted as a sequence of alphabet characters.

Key Points to Consider:

A digit '0' without a preceding '1' or '2' cannot be mapped to any character since there are no characters encoded as "0" or "06".
The string can be decoded using single digits (e.g., "12" can be "1" + "2" -> "AB") or by valid two-digit combinations (e.g., "12" can also be "12" -> "L").
Dynamic programming can help keep track of the number of ways to decode up to a certain point in the string.

Dynamic Programming Concept:

We'll use a list

dp

where

dp[i]

represents the number of ways to decode the substring

s[:i]

. The size of

dp

will be

n + 1

to handle the base case where no characters are decoded yet (

dp[0]

Steps:

Initialize
dp[0]

to 1 as the base case, representing the one way to decode an empty string.
Initialize
dp[1]

to 1 if the first character is not '0', because a single valid first character has exactly one way to be decoded.
For each subsequent character in the string (starting from index 2), check:

If the current character is not '0', the current position can take the number of ways till the previous position (
dp[i] = dp[i-1]

).
If the two-character combination ending at the current position forms a valid mapping (i.e., falls between "10" and "26"), add the ways from two positions back (
dp[i] += dp[i-2]

).

Detailed Steps in Pseudocode

Next, let's translate this logic into pseudocode with comments explaining each step:

                                            
function numDecodings(encoded_string):
    # Return 0 if the very first character is '0' since it can't be decoded.
    if encoded_string is empty or encoded_string starts with '0':
        return 0
    
    # Define the length of the string
    string_length = length of encoded_string
    
    # Create a list to hold the number of ways to decode up to each point
    decoding_ways = list of size string_length + 1 initialized to 0
    
    # There's 1 way to decode an empty string
    decoding_ways[0] = 1
    
    # There's 1 way to decode the string if the first character is not '0'
    decoding_ways[1] = 1
    
    # Loop over each character starting from the second one
    for index from 2 to string_length (inclusive):
        # If current character encoded_string[index - 1] is not '0'
        if encoded_string[index - 1] is not '0':
            # Increment current ways by the ways at the previous position
            decoding_ways[index] += decoding_ways[index - 1]
        
        # Check if the two-character substring ending at current position is valid (10 to 26)
        if the substring from index - 2 to index (encoded_string[index - 2:index]) is between "10" and "26" inclusive:
            # Increment current ways by the ways from two positions back
            decoding_ways[index] += decoding_ways[index - 2]
    
    # The result is the number of ways to decode the entire string
    return decoding_ways[string_length]

This pseudocode walks through every character and considers both single and two-digit decodings, incrementally building the solution using previously computed values to make sure every possible valid decoding combination is accounted for. The dynamic nature ensures efficiency, preventing redundant computations, and constructs the count in an optimal manner.