Decoding a digit sequence into meaningful characters is a common problem in coding interviews and competitive programming. This article explores how to determine the number of possible decodings for a given sequence of digits.
Each digit from 1 to 26 corresponds to a letter in the alphabet:
Input:
digits[] = "123"
Output:
3
Possible Decodings:
Input:
digits[] = "121"
Output:
3
Possible Decodings:
count = 0
.#include <iostream>
using namespace std;
int countDecodings(string digits, int n) {
if (n == 0 || n == 1) return 1;
if (digits[0] == '0') return 0;
int count = 0;
if (digits[n - 1] > '0')
count = countDecodings(digits, n - 1);
if (digits[n - 2] == '1' || (digits[n - 2] == '2' && digits[n - 1] < '7'))
count += countDecodings(digits, n - 2);
return count;
}
int main() {
string digits = "121";
cout << "Total Decodings: " << countDecodings(digits, digits.size());
return 0;
}
class DecodeWays {
static int countDecodings(String digits) {
int n = digits.length();
if (n == 0 || digits.charAt(0) == '0') return 0;
int[] dp = new int[n + 1];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; i++) {
if (digits.charAt(i - 1) > '0')
dp[i] = dp[i - 1];
int twoDigit = Integer.parseInt(digits.substring(i - 2, i));
if (twoDigit >= 10 && twoDigit <= 26)
dp[i] += dp[i - 2];
}
return dp[n];
}
public static void main(String[] args) {
String digits = "123";
System.out.println("Total Decodings: " + countDecodings(digits));
}
}
O(2^n)
(can be optimized using memoization)O(n)
(better efficiency)Understanding how to count decodings of a digit sequence is essential for mastering dynamic programming and recursion. The recursive approach provides an intuitive understanding, while dynamic programming ensures efficiency. By implementing these methods, you can solve similar problems related to string decoding and encoding.
n
people occupy r
seats in a theater