Skip to main content

DECODE WAYS - LEETCODE PROBLEM 91

 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; 
}
}




https://leetcode.com/problems/decode-ways/

Comments

.

Popular posts from this blog

Nth Node from End in LinkedList

Nth Node from End in LinkedList 1)  Find length of  linked list. 2) Traverse (length-position+1) element from begin. //nth Node from end public Node nodeFromEnd ( Node head , int position ){ Node temp = head ; int length = 1 ; while ( temp . next != null ) { length ++; temp = temp . next ; } System . out . println ( "length" + length ); temp = head ; int c = 1 ; while ( c !=( length - position + 1 )) { temp = temp . next ; c ++; } return temp ; }