Monday, 26 August 2013

Decode the given string

Given a input encoded string find the no. of ways it can be decoded.(we encode A-1 , B-2 , C-3...)

Example:
Input : "311316" (encoded string)
output : 6 

How? 
 word CAMP encoded as 311316. It can be decoded as 3 11 3 16 (CKCP), 3 1 1 3 16(CAACP) , 3 1 1 3 1 6 , (CAACAF) . 3 1 13 16(CAMP),  3 1 13 1 6(CAMAF), 3 11 3 1 6 (CKCAF).

Algorithm : 
    1. Initialize the Array array of size N with 0.
    2. array[0] = 1
    3. for i = 1 to N (N is length of given input string)
        a) If value of current single character is less than or equal to 26 Then
               array[i] = array[i-1]
        b) If value of current element and previous element is less than or equal to 26 Then
               array[i] += array[i-2]

Implementation:

class Alphacode{
static int ways(String input){
                //Boundary condition check
if(input == null || input.length() == 0)
return 0;

int []arr = new int[input.length() ];
arr[0] = 1;

for(int i = 1; i < input.length(); i++){
int singleDigit = input.charAt(i) - '0';  //check for single digit value
if(singleDigit  <= 26)
arr[i] = arr[i-1];

int doubleDigit = Integer.parseInt(input.substring(i-1, i+1));  //check for double digit value
if(doubleDigit  <= 26 )
if( i== 1)
arr[i] = arr[i-1]+1;
else
arr[i] += arr[i-2];

}
return arr[input.length()-1];
}

public static void main(String... args){
String input= "25114";
int ways = ways(input);
System.out.println(ways);
}
}

4 comments:

  1. The return value should be arr[input.length()-1]

    Also, the following 2 lines of code are not needed, since anyway, all single digits are valid codes for some alphabet between A and I. As I understand, you have these only for better readability :)

    int singleDigit = input.charAt(i) - '0'; //check for single digit value
    if(singleDigit <= 26)

    ReplyDelete
    Replies
    1. Thanks for pointing this out. I have updated the post.

      Delete
  2. You blog is informative :)
    codes here are really simple :)
    I like your blog

    ReplyDelete