Find all possible interpretations of an array of digits | GeeksforGeeks

Find all possible interpretations of an array of digits | GeeksforGeeks
Consider a coding system for alphabets to integers where ‘a’ is represented as 1, ‘b’ as 2, .. ‘z’ as 26. Given an array of digits (1 to 9) as input, write a function that prints all valid interpretations of input array.

                           “” {1,2,1}            Codes used in tree
                       /             \               "a" --> 1
                      /               \              "b" --> 2 
                  "a"{2,1}            "l"{1}         "l" --> 12
                 /        \          /     \
                /          \        /       \
            "ab"{1}        "au"    "la"      null
             /    \
            /      \
         "aba"      null

The idea here is string can take at-most two paths:
1. Proces single digit
2. Process two digits
That means we can use binary tree here. Processing with single digit will be left child and two digits will be right child. If value two digits is greater than 26 then our right child will be null as we don’t have alphabet for greater than 26.

Also check http://www.tuicool.com/articles/mAzAbmv

public static Node createTree(int data, String pString, int[] arr) {

        // Invalid input as alphabets maps from 1 to 26

        if (data > 26)

            return null;

        // Parent String + String for this node

        String dataToStr = pString + alphabet[data];

        Node root = new Node(dataToStr);

        // if arr.length is 0 means we are done

        if (arr.length != 0) {

            data = arr[0];

            // new array will be from index 1 to end as we are consuming

            // first index with this node

            int newArr[] = Arrays.copyOfRange(arr, 1, arr.length);

            // left child

            root.left = createTree(data, dataToStr, newArr);

            // right child will be null if size of array is 0 or 1

            if (arr.length > 1) {

                data = arr[0] * 10 + arr[1];

                // new array will be from index 2 to end as we

                // are consuming first two index with this node

                newArr = Arrays.copyOfRange(arr, 2, arr.length);

                root.right = createTree(data, dataToStr, newArr);

            }

        }

        return root;

    }

    // To print out leaf nodes

    public static void printleaf(Node root) {

        if (root == null)

            return;

        if (root.left == null && root.right == null)

            System.out.print(root.getDataString() + "  ");

         

        printleaf(root.left);

        printleaf(root.right);

    }

    // The main function that prints all interpretations of array

    static void printAllInterpretations(int[] arr) {

        // Step 1: Create Tree

        Node root = createTree(0, "", arr);

        // Step 2: Print Leaf nodes

        printleaf(root);

        System.out.println();  // Print new line

    }

https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/InterpretationOfArray.java
    public void interpret(int arr[]){
        char t[][] = new char[arr.length][2];
        for(int i=0; i < arr.length; i++){
            for(int j=0; j < 2; j++){
                t[i][j] = '0';
            }
        }
        for(int l=1; l <=2; l++){
            for(int i=0; i <= arr.length -l ; i++){
                int j = i + l-1;
                t[i][l-1] = getRepresentation(i == j ? arr[i] : arr[i]*10 +arr[j]);
            }
        }
        List<Character> result = new ArrayList<Character>();
        interpret(arr.length,0,result,t);
    }
 
    private void interpret(int len,int pos,List<Character> result,char[][] t){
        if(pos== len){
            print(result);
            return;
        }
        if(t[pos][0] != '0'){
            result.add(t[pos][0]);
            interpret(len,pos+1,result,t);
            result.remove(result.size()-1);
        }
     
        if(pos+1 < len && t[pos][1] != '0'){
            result.add(t[pos][1]);
            interpret(len, pos+2, result, t);
            result.remove(result.size()-1);
        }
         
    }
 
    private void print(List<Character> result){
        for(int i=0; i < result.size(); i++){
            System.out.print(result.get(i) + " ");
        }
        System.out.println();
    }
 
    private char getRepresentation(int number){
        if(number > 26 || number <= 0){
            return '0';
        }
        return (char)('a' + number -1);
    }

    public int numberOfWaysPossible(int input[],int pos){
        if(pos > input.length){
            return 0;
        }
        if(pos == input.length){
            return 1;
        }
       
https://github.com/mission-peace/interview/blob/master/src/com/interview/recursion/PrintArrayInAdjacentWay.java       
        int count = numberOfWaysPossible(input,pos+1);
        if(pos + 1 < input.length){
            int num = input[pos]*10 + input[pos+1];
            if(num < 27){
                count += numberOfWaysPossible(input, pos+2);
            }
        }
        return count;
    }
   
    /**
     * Since we know this is same as fibonacci series all we have to do is either use sum of last two numbers if
     * total is less than equal to 26 or use just last number if total is greater than 26
     * total is calculated by creating a number from current number and previous number
     * @param input
     * @return
     */
    public int numberOfWaysPossibleFaster(int input[]){
        int a0 = 1;
        int a1 = 1;
        int c = 0;
        for(int i=1; i < input.length; i++){
            if(input[i] + input[i-1]*10 <=26){
                c = a1 + a0;
            }else{
                c = a1;
            }
            a0 = a1;
            a1 = c;
        }
        return c;
    }
Read full article from Find all possible interpretations of an array of digits | GeeksforGeeks