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

BREADTH FIRST SEARCH IN JAVA

BREADTH FIRST SEARCH IN JAVA:- package com . problems . graph ; import java.awt.DisplayMode ; import java.util.Iterator ; import java.util.LinkedList ; public class BFSGraph { int maxsize ; Vertex vertexlist []; int matrixlist [][]; int vertexcount ; @SuppressWarnings ({ "rawtypes" , "unused" }) LinkedList queue ; public BFSGraph () { maxsize = 20 ; matrixlist = new int [ maxsize ][ maxsize ]; vertexlist = new Vertex [ maxsize ]; for ( int i = 0 ; i < maxsize ; i ++) { for ( int j = 0 ; j < maxsize ; j ++) { matrixlist [ i ][ j ]= 0 ; } } queue = new LinkedList (); } public void addVertex ( char label ) { vertexlist [ vertexcount ++]= new Vertex ( label ); } public void addEdge ( int i , int j ) { matrixlist [ i ][ j ]= 1 ; matrixlist [ j ][ i ]= 1 ; } public void displayVertex ( int v ) { System . out . println ( vertexlis

How to do Effective Programming?

There is no secret to doing effective programming but following a sequence of steps and procedures can help in building great programs. Today I will take you on a tour to some of the best practices that are integrants of perfect programs. Algorithms are important: - You can’t deny the fact that algorithms are important and before start to write any program, Algorithms are must to write. For example, if there is a program about finding the sum of two numbers? What will you write ?The steps can be :- 1)   Get the first number. 2)   Get the second number. 3)   Add both numbers. This is what algorithm is writing about ,a list of statements .From the above three statements you can conclude boundary cases (at least two number should be there in input), mathematical function(Sum is needed here) , storage capacity(amount of memory to be assign to the variables), number of methods by analyzing repeat steps (reduce replete codes) and many other things. During algorithm only yo