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.
Examples
Input: {1, 1}
Output: ("aa", 'k")
[2 interpretations: aa(1, 1), k(11)]
Input: {1, 2, 1}
Output: ("aba", "au", "la")
[3 interpretations: aba(1,2,1), au(1,21), la(12,1)]
Input: {9, 1, 8}
Output: {"iah", "ir"}
[2 interpretations: iah(9,1,8), ir(9,18)]
Please note we cannot change order of array. That means {1,2,1} cannot become {2,1,1}
On first look it looks like a problem of permutation/combination. But on closer look you will figure out that this is an interesting tree problem.
The idea here is string can take at-most two paths:
1. Process 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.
Let’s understand with an example .Array a = {1,2,1}. Below diagram shows that how our tree grows.
“” {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
Braces {} contain array still pending for processing. Note that with every level, our array size decreases. If you will see carefully, it is not hard to find that tree height is always n (array size)
How to print all strings (interpretations)? Output strings are leaf node of tree. i.e for {1,2,1}, output is {aba au la}.
We can conclude that there are mainly two steps to print all interpretations of given integer array.
Step 1: Create a binary tree with all possible interpretations in leaf nodes.
Step 2: Print all leaf nodes from the binary tree created in step 1.
Following is Java implementation of above algorithm.
C++
// A C++ program to print all interpretations of an integer// array#include <iostream>#include <vector>using namespace std;// A class to represent a binary tree nodeclass Node { public: string data_str; Node* left; Node* right; Node(string data_str) { this->data_str = data_str; left = right = NULL; } string get_data_str() { return data_str; }};// Method to create a binary tree which stores all// interpretations of arr[] in leaf nodesNode* create_tree(int data, string p_str, vector<int>& arr){ // Invalid input as alphabets maps from 1 to 26 if (data > 26) { return NULL; } // Parent String + String for this node string data_to_str = p_str + (char)('a' + data - 1); Node* root = new Node(data_to_str); // if arr length is 0 means we are done if (arr.size() != 0) { data = arr[0]; // new array will be from index 1 to end as we are // consuming first index with this node vector<int> new_arr(arr.begin() + 1, arr.end()); // left child root->left = create_tree(data, data_to_str, new_arr); // right child will be NULL if size of array is 0 or // 1 if (arr.size() > 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 vector<int> new_arr(arr.begin() + 2, arr.end()); root->right = create_tree(data, data_to_str, new_arr); } } return root;}// To print out leaf nodesvoid print_leaf(Node* root){ if (root == NULL) { return; } if (root->left == NULL && root->right == NULL) { cout << root->get_data_str() << " "; } print_leaf(root->left); print_leaf(root->right);}// The main function that prints all interpretations of// arrayvoid printAllInterpretations(vector<int>& arr){ // Step 1: Create Tree Node* root = create_tree(0, "", arr); // Step 2: Print Leaf nodes print_leaf(root); cout << endl; // Print new line}int main(){ // For simplicity I am taking it as string array. Char // Array will save space vector<string> alphabet = { "", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z" }; // Driver code to test above methods // aacd(1,1,3,4) amd(1,13,4) kcd(11,3,4) // Note : 1,1,34 is not valid as we don't have values // corresponding to 34 in alphabet vector<int> arr = { 1, 1, 3, 4 }; printAllInterpretations(arr); vector<int> arr2 = { 1, 1, 1 }; printAllInterpretations(arr2); vector<int> arr3 = { 2, 6 }; printAllInterpretations(arr3); vector<int> arr4 = { 1, 2 }; printAllInterpretations(arr4); vector<int> arr5 = { 1, 0 }; printAllInterpretations(arr5); vector<int> arr6 = {}; printAllInterpretations(arr6); vector<int> arr7 = { 1, 2, 2, 1 }; printAllInterpretations(arr7);} |
Java
// A Java program to print all interpretations of an integer arrayimport java.util.Arrays;// A Binary Tree nodeclass Node { String dataString; Node left; Node right; Node(String dataString) { this.dataString = dataString; //Be default left and right child are null. } public String getDataString() { return dataString; }}public class arrayToAllInterpretations { // Method to create a binary tree which stores all interpretations // of arr[] in lead nodes 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 } // For simplicity I am taking it as string array. Char Array will save space private static final String[] alphabet = {"", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "v", "z"}; // Driver method to test above methods public static void main(String args[]) { // aacd(1,1,3,4) amd(1,13,4) kcd(11,3,4) // Note : 1,1,34 is not valid as we don't have values corresponding // to 34 in alphabet int[] arr = {1, 1, 3, 4}; printAllInterpretations(arr); // aaa(1,1,1) ak(1,11) ka(11,1) int[] arr2 = {1, 1, 1}; printAllInterpretations(arr2); // bf(2,6) z(26) int[] arr3 = {2, 6}; printAllInterpretations(arr3); // ab(1,2), l(12) int[] arr4 = {1, 2}; printAllInterpretations(arr4); // a(1,0} j(10) int[] arr5 = {1, 0}; printAllInterpretations(arr5); // "" empty string output as array is empty int[] arr6 = {}; printAllInterpretations(arr6); // abba abu ava lba lu int[] arr7 = {1, 2, 2, 1}; printAllInterpretations(arr7); }} |
Python3
# A Python program to print all interpretations of an integer arrayfrom typing import List# A class to represent a binary tree nodeclass Node: def __init__(self, data_str: str): self.data_str = data_str self.left = None self.right = None def get_data_str(self) -> str: return self.data_str# Method to create a binary tree which stores all interpretations of arr[] in leaf nodesdef create_tree(data: int, p_str: str, arr: List[int]) -> Node: # Invalid input as alphabets maps from 1 to 26 if data > 26: return None # Parent String + String for this node data_to_str = p_str + alphabet[data] root = Node(data_to_str) # if arr length is 0 means we are done if len(arr) != 0: data = arr[0] # new array will be from index 1 to end as we are consuming # first index with this node new_arr = arr[1:] # left child root.left = create_tree(data, data_to_str, new_arr) # right child will be None if size of array is 0 or 1 if len(arr) > 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 new_arr = arr[2:] root.right = create_tree(data, data_to_str, new_arr) return root# To print out leaf nodesdef print_leaf(root: Node) -> None: if root is None: return if root.left is None and root.right is None: print(root.get_data_str(), end=" ") print_leaf(root.left) print_leaf(root.right)# The main function that prints all interpretations of arraydef printAllInterpretations(arr: List[int]) -> None: # Step 1: Create Tree root = create_tree(0, "", arr) # Step 2: Print Leaf nodes print_leaf(root) print() # Print new line# For simplicity I am taking it as string array. Char Array will save spacealphabet = ["", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "v", "z"]# Driver code to test above methodsif __name__ == "__main__": # aacd(1,1,3,4) amd(1,13,4) kcd(11,3,4) # Note : 1,1,34 is not valid as we don't have values corresponding # to 34 in alphabet arr = [1, 1, 3, 4] printAllInterpretations(arr) # aaa(1,1,1) ak(1,11) ka(11,1) arr2 = [1, 1, 1] printAllInterpretations(arr2) arr3 = [2, 6] printAllInterpretations(arr3) arr4 = [1, 2] printAllInterpretations(arr4) arr5 = [1, 0] printAllInterpretations(arr5) arr6 = [] printAllInterpretations(arr6) arr7 = [1, 2, 2, 1] printAllInterpretations(arr7) |
Javascript
// A class to represent a binary tree nodeclass Node { constructor(data_str) { this.data_str = data_str; this.left = null; this.right = null; } get_data_str() { return this.data_str; }}// Method to create a binary tree which stores all interpretations of arr[] in leaf nodesfunction createTree(data, p_str, arr) { // Invalid input as alphabets maps from 1 to 26 if (data > 26) { return null; } // Parent String + String for this node let data_to_str = p_str + alphabet[data]; let root = new Node(data_to_str); // 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 let new_arr = arr.slice(1); // left child root.left = createTree(data, data_to_str, new_arr); // right child will be None 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 new_arr = arr.slice(2); root.right = createTree(data, data_to_str, new_arr); } } return root;}// To print out leaf nodesfunction printLeaf(root) { if (root === null) { return; } if ((root.left === null) && (root.right === null)) { console.log(root.get_data_str(), end=" "); } printLeaf(root.left); printLeaf(root.right);}// The main function that prints all interpretations of arrayfunction printAllInterpretations(arr) { // Step 1: Create Tree let root = createTree(0, "", arr); // Step 2: Print Leaf nodes let output = '' function printLeafHelper(root) { if (root === null) { return; } if ((root.left === null) && (root.right === null)) { output += root.get_data_str() + ' '; } printLeafHelper(root.left); printLeafHelper(root.right); } printLeafHelper(root); console.log(output); // Print Output}// For simplicity I am taking it as string array. Char Array will save spacelet alphabet = ["", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "v", "z"];// Driver code to test above methods // aacd(1,1,3,4) amd(1,13,4) kcd(11,3,4) // Note : 1,1,34 is not valid as we don't have values corresponding // to 34 in alphabet let arr = [1, 1, 3, 4]; printAllInterpretations(arr); // aaa(1,1,1) ak(1,11) ka(11,1) let arr2 = [1, 1, 1]; printAllInterpretations(arr2); let arr3 = [2, 6]; printAllInterpretations(arr3); let arr4 = [1, 2]; printAllInterpretations(arr4); let arr5 = [1, 0]; printAllInterpretations(arr5); let arr6 = []; printAllInterpretations(arr6); let arr7 = [1, 2, 2, 1]; printAllInterpretations(arr7); |
C#
// A C# program to print all interpretations of an integer// arrayusing System;using System.Collections.Generic;// A class to represent a binary tree nodeclass Node { public string data_str; public Node left; public Node right; public Node(string data_str) { this.data_str = data_str; left = right = null; } public string get_data_str() { return data_str; }}class Program { // Method to create a binary tree which stores all // interpretations of arr[] in leaf nodes static Node create_tree(int data, string p_str, List<int> arr) { // Invalid input as alphabets maps from 1 to 26 if (data > 26) { return null; } // Parent String + String for this node string data_to_str = p_str + (char)('a' + data - 1); Node root = new Node(data_to_str); // if arr length is 0 means we are done if (arr.Count != 0) { data = arr[0]; // new array will be from index 1 to end as we // are consuming first index with this node List<int> new_arr = arr.GetRange(1, arr.Count - 1); // left child root.left = create_tree(data, data_to_str, new_arr); // right child will be NULL if size of array is // 0 or 1 if (arr.Count > 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 new_arr = arr.GetRange(2, arr.Count - 2); root.right = create_tree(data, data_to_str, new_arr); } } return root; } // To print out leaf nodes static void print_leaf(Node root) { if (root == null) { return; } if (root.left == null && root.right == null) { Console.Write(root.get_data_str() + " "); } print_leaf(root.left); print_leaf(root.right); } // The main function that prints all interpretations of // array static void printAllInterpretations(List<int> arr) { // Step 1: Create Tree Node root = create_tree(0, "", arr); // Step 2: Print Leaf nodes print_leaf(root); Console.WriteLine(); // Print new line } static void Main(string[] args) { // For simplicity I am taking it as string array. // Char Array will save space List<string> alphabet = new List<string>{ "", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z" }; // Driver code to test above methods // aacd(1,1,3,4) amd(1,13,4) kcd(11,3,4) // Note : 1,1,34 is not valid as we don't have // values corresponding to 34 in alphabet List<int> arr = new List<int>{ 1, 1, 3, 4 }; printAllInterpretations(arr); arr = new List<int>{ 1, 1, 1 }; printAllInterpretations(arr); arr = new List<int>{ 2, 6 }; printAllInterpretations(arr); arr = new List<int>{ 1, 2 }; printAllInterpretations(arr); arr = new List<int>{ 1, 0 }; printAllInterpretations(arr); arr = new List<int>{}; printAllInterpretations(arr); arr = new List<int>{ 1, 2, 2, 1 }; printAllInterpretations(arr); }} |
Output
`aacd `amd `kcd `aaa `ak `ka `bf `z `ab `l `a` `j ` `abba `abu `ava `lba `lu
Output:
aacd amd kcd aaa ak ka bf z ab l a j abba abu ava lba lu
Time complexity is O(2^n), where n is the length of the input array.
The auxiliary space is O(n^2), where n is the length of the input array.
Exercise:
1. What is the time complexity of this solution? [Hint : size of tree + finding leaf nodes]
2. Can we store leaf nodes at the time of tree creation so that no need to run loop again for leaf node fetching?
3. How can we reduce extra space?
This article is compiled by Varun Jain. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Method 2 : ( using backtracking )
This problem can be solved using backtracking . One of the basic intuition is that all the numbers we are going to generate using digits of the input array must lie in between the range of [ 1 , 26 ] both inclusive . So in a bruteforce way we try all the possible combinations and if the number generated so far lies in between the range of [ 1 , 26 ] we append the corresponding alphabet and recur for the remaining string and we pop the appended character ( backtrack ) to find all the valid interpretations . In this process if we reach the end of the string that means we have found 1 possible interpretation . But at any point of time if we find the number generated so far is greater than 26 we need not to proceed further because that is not a valid number to interpret , so in that case we backtrack and try for the rest of the combinations .
Below is the C++ implementation
C++
#include <bits/stdc++.h>using namespace std;string dup;// function which returns all the valid interpretationsvoid compute(int arr[], int n, vector<string>& vect, int s){ // cout << "ex" << endl; /* if we reach the end of the string than we have found 1 valid interpretation */ if (s == n) { // store it in the vector vect.push_back(dup); /* since we have reached the end of the string there is no string to recur so return */ return; } // initialize the num with zero int num = 0; for (int i = s; i < n; i++) { // generate the number num = num * 10 + arr[i]; /* validate the number generated so far */ if (num >= 1 and num <= 26) { // append the corresponding alphabet dup += ('a' + (num - 1)); // recur for the remaining string compute(arr, n, vect, i + 1); // backtrack to find rest of the combinations dup.pop_back(); } // if the number generated so far if greater // than 26 we need not to proceed further // as it cannot be used to make a valid // interpretation else break; } return;}vector<string> findAllInterpretations(int n, int arr[]){ // vector to store all the valid interpretations vector<string> vect; dup = ""; compute(arr, n, vect, 0); // return all valid interpretations return vect;}int main(){ int n; cin >> n; int* arr = new int[n]; for (int i = 0; i < n; i++) { cin >> arr[i]; } vector<string> res; res = findAllInterpretations(n, arr); int m = res.size(); for (int i = 0; i < m; i++) { cout << res[i] << " "; } return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class Main { private static String dup = ""; // function which returns all the valid interpretations private static void compute(int[] arr, int n, List<String> vect, int s) { // If we reach the end of the string, // then we have found 1 valid interpretation if (s == n) { // store it in the list vect.add(dup); /* since we have reached the end of the string there is no string to recur so return */ return; } // initialize the num with zero int num = 0; for (int i = s; i < n; i++) { // generate the number num = num * 10 + arr[i]; /* validate the number generated so far */ if (num >= 1 && num <= 26) { // append the corresponding alphabet dup += (char) ('a' + (num - 1)); // recur for the remaining string compute(arr, n, vect, i + 1); // backtrack to find rest of the combinations dup = dup.substring(0, dup.length() - 1); } // if the number generated so far if greater than 26 we need not to proceed further // as it cannot be used to make a valid interpretation else break; } return; } private static List<String> findAllInterpretations(int n, int[] arr) { // List to store all the valid interpretations List<String> vect = new ArrayList<>(); dup = ""; compute(arr, n, vect, 0); // return all valid interpretations return vect; } public static void main(String[] args) { int n = 5; int[] arr = new int[]{1, 2, 3, 4, 5}; List<String> res = findAllInterpretations(n, arr); for (String s : res) { System.out.print(s + " "); } }} |
Python3
def compute(arr, n, vect, s, dup): """ Helper function to compute all the valid interpretations of the given array. """ if s == n: # store the valid interpretation in the vector vect.append(dup) # return as we have reached the end of the array return # initialize the number with zero num = 0 for i in range(s, n): # generate the number num = num * 10 + arr[i] # validate the number generated so far if 1 <= num <= 26: # append the corresponding alphabet dup += chr(ord('a') + num - 1) # recur for the remaining array compute(arr, n, vect, i + 1, dup) # backtrack to find rest of the combinations dup = dup[:-1] # if the number generated so far is greater than 26, # we need not proceed further as it cannot be used to make a valid interpretation else: break returndef findAllInterpretations(n, arr): """ Function to find all the valid interpretations of the given array. """ # vector to store all the valid interpretations vect = [] # empty string to store the interpretations dup = "" compute(arr, n, vect, 0, dup) # return all valid interpretations return vectif __name__ == "__main__": n = int(input()) arr = list(map(int, input().split())) res = findAllInterpretations(n, arr) for interpretation in res: print(interpretation, end=" ") print() |
C#
using System;using System.Collections.Generic;class Program { static string dup; // function which returns all the valid interpretations static void Compute(int[] arr, int n, List<string> vect, int s) { // if we reach the end of the string // than we have found 1 valid interpretation if (s == n) { // store it in the vector vect.Add(dup); // since we have reached the end of the string // there is no string to recur so return return; } // initialize the num with zero int num = 0; for (int i = s; i < n; i++) { // generate the number num = num * 10 + arr[i]; // validate the number generated so far if (num >= 1 && num <= 26) { // append the corresponding alphabet dup += (char)('a' + (num - 1)); // recur for the remaining string Compute(arr, n, vect, i + 1); // backtrack to find rest of the // combinations dup = dup.Remove(dup.Length - 1); } // if the number generated so far if greater // than 26 we need not to proceed further // as it cannot be used to make a valid // interpretation else { break; } } return; } static List<string> FindAllInterpretations(int n, int[] arr) { // vector to store all the valid interpretations List<string> vect = new List<string>(); dup = ""; Compute(arr, n, vect, 0); // return all valid interpretations return vect; } static void Main(string[] args) { int n = 5; int[] arr = new int[] { 1, 2, 3, 4, 5 }; List<string> res = FindAllInterpretations(n, arr); foreach(string s in res) { Console.Write(s + " "); } }} |
Javascript
function compute(arr, n, vect, s, dup) { // if we reach the end of the string // than we have found 1 valid interpretation if (s == n) { // store it in the vector vect.push(dup); // since we have reached the end of the string // there is no string to recur so return return; } // initialize the num with zero let num = 0; for (let i = s; i < n; i++) { // generate the number num = num * 10 + arr[i]; // validate the number generated so far if (num >= 1 && num <= 26) { // append the corresponding alphabet dup += String.fromCharCode('a'.charCodeAt(0) + (num - 1)); // recur for the remaining string compute(arr, n, vect, i + 1, dup); // backtrack to find rest of the // combinations dup = dup.slice(0, -1); } // if the number generated so far if greater // than 26 we need not to proceed further // as it cannot be used to make a valid // interpretation else { break; } } return;}function findAllInterpretations(n, arr) { // vector to store all the valid interpretations const vect = []; let dup = ""; compute(arr, n, vect, 0, dup); // return all valid interpretations return vect;}const n = 5;const arr = [1, 2, 3, 4, 5];const res = findAllInterpretations(n, arr);console.log(res.join(" ")); |
Input : 5 1 1 2 1 2
The time complexity is O(2^n),
The auxiliary space is also O(2^n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
