A message containing letters from A-Z
is being encoded to numbers using the following mapping:
'A' -> 1 'B' -> 2 ... 'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
class Solution {
public int numDecodings(String s) {
int ways=0;
ways=countDecoding(s.toCharArray(),s.length());
return ways;
}
int countDecoding(char[] digits, int n){
// System.out.println(" digits "+disgits[0]);
// for base condition "01123" should return 0
// base cases
if (n == 0 || (n == 1 && digits[0]!='0'))
return 1;
if (digits[0]=='0') {
return 0;
}
// Initialize count
int count = 0;
// If the last digit is not 0, then
// last digit must add to
// the number of words
if(digits[n - 1] > '0')
count = countDecoding(digits, n - 1);
// If the last two digits form a number
// smaller than or equal to 26,
// then consider last two digits and recur
if (digits[n - 2] == '1' || (digits[n - 2] == '2' && digits[n - 1] < '7'))
count += countDecoding(digits, n - 2);
return count;
}
}
Comments
Post a Comment