## Facebook Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
11
of 11 vote

call

``decode("", "1123");``

``````public Set<String> decode(String prefix, String code) {
Set<String> set = new HashSet<String>();
if (code.length() == 0) {
return set;
}

if (code.charAt(0) == '0')
return set;

set.addAll(decode(prefix + (char) (code.charAt(0) - '1' + 'a'),
code.substring(1)));
if (code.length() >= 2 && code.charAt(0) == '1') {
prefix + (char) (10 + code.charAt(1) - '1' + 'a'),
code.substring(2)));
}
if (code.length() >= 2 && code.charAt(0) == '2'
&& code.charAt(1) <= '6') {
prefix + (char) (20 + code.charAt(1) - '1' + 'a'),
code.substring(2)));
}
return set;
}``````

Comment hidden because of low score. Click to expand.
3

Is there any chance to optimize, e.g. DP?

Comment hidden because of low score. Click to expand.
0

What is the complexity of this?

Comment hidden because of low score. Click to expand.
1
of 1 vote

@jerryyue1908 - Yes it is possible to optimize with DP. The optimization will be to memoize the result of decode on a substring (e.g. "123" in "121123"). This way, whenever decode("123") is called, the previous result can be retrieved instead of doing the computation over again.

Comment hidden because of low score. Click to expand.
2

@jerryyue1908 here is the DP version of it -

``````public static int DP(int []a, int n) {
int [] dp = new int [n+1];
dp[0] = 0;

for(int i=1; i<=n; i++) {
if(i>1 && a[i-2] <= 2 && a[i-1] <= 6) {
dp[i] = dp[i-1] + dp[i-2] + 1;
} else {
dp[i] = dp[i-1];
}
}
return dp[n]+1; // +1 for base case where all characters are made of single digits
}``````

It is easy to generate all strings from dp matrix. However, it will take same time as generating from the given array. So I wrote simple code for generating strings from the given array, which returns the number of strings as well -

``````public static int print(int [] a, int i, int n, String s) {
if(i == n)  {
System.out.println(s);
return 0;
}

int ans = 0;
if(i < n-1 && a[i+1] <= 6 && a[i] <= 2) {
ans += print(a, i+2, n, new String(s+(char)(a[i]*10+a[i+1]+'a'-1))) +1;
}
ans += print(a, i+1, n, new String(s+(char)(a[i]+'a'-1)));
return ans;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

@xq - time complexity of DP solution is O(n) as you calculate each i only once.
time complexity of recursive method is 2^(n-1) worst case.

Worst case is: {2,2,2,2} when at each first n-1 positions you have two options - either eat just current digit, or eat the next digit also.

Comment hidden because of low score. Click to expand.
0

@HauntedGhost
Got a feeling there might be a little bug: 19 is still a valid letter code, but the if will not consider it as 2 digit code. try {1,9}, should return both "ai" and "s".
I'd suggest changing the if slightly toif(i < n-1 && ( (a[i+1] <= 6 && a[i] == 2) ||
(a[i+1] <= 9 && a[i] == 1)) )

Comment hidden because of low score. Click to expand.
3
of 3 vote

Basically, just go through the string recursively, always eating one and two characters (where possible).

``````package a1;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class GenAllCodes {

public static void main(String[] args) {
for(String str : decode("1123"))
{
System.out.println(str);
}
}

public static Set <String> decode(String in)
{
char curChar = 'a';
Map <Integer, Character> numberToChar = new HashMap<>();
for(int i = 1; i <= 26; i++)
{
numberToChar.put(i, curChar);
curChar++;
}
return decodeHelper(numberToChar, in, 0, new ArrayList<Character>());
}

private static Set<String> decodeHelper(Map <Integer, Character> numberToChar,
String in, int charAt,
ArrayList<Character> arrayList) {
Set <String> result = new HashSet<>();
if(charAt >= in.length())
{
String str = "";
for(char c : arrayList)
{
str += c;
}
return result;
}
else
{
int charCode = Integer.valueOf(in.charAt(charAt) + "");
char curChar = numberToChar.get(charCode);
arrayList.remove(arrayList.size()-1);
if(in.length() > charAt+1)
{
charCode = Integer.valueOf(in.substring(charAt, charAt+2));
if(charCode <= 26)
{
curChar = numberToChar.get(charCode);
arrayList.remove(arrayList.size()-1);
}
}
}
return result;
}

}``````

Comment hidden because of low score. Click to expand.
0

Looks good to me. How long did it take you ? I had roughly 30 minutes to finish this on whiteboard and I didn't do a good job.

Comment hidden because of low score. Click to expand.
1
of 1 vote

@Anonymous: small correction....... your code doesn't work for "1020". or any input that can have 10/20.

Here is the working and modified code.....

package com.rakesh.topcoder;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class GenAlphabetCodes {

public static void main(String[] args) {
// TODO Auto-generated method stub

Scanner input = new Scanner(System.in);
System.out
.println("Please enter any length number but combination of 1 to 26 ....... ");
String val = input.next();

System.out.println("All possible Alphabet codes for the give Number: "
+ val);
for (String string : decode(val)) {
System.out.println(string);
}

}

public static Set<String> decode(String in) {
char curChar = 'a';
Map<Integer, Character> numberToChar = new HashMap<Integer, Character>();
for (int i = 1; i <= 26; i++) {
numberToChar.put(i, curChar);
curChar++;
}
return decodeHelper(numberToChar, in, 0, new ArrayList<Character>());
}

private static Set<String> decodeHelper(
Map<Integer, Character> numberToChar, String in, int charAt,
ArrayList<Character> arrayList) {
Set<String> result = new HashSet<String>();
if (charAt >= in.length()) {
String str = "";
for (char c : arrayList) {
str += c;
}
return result;
} else {
int charCode = Integer.valueOf(in.charAt(charAt) + "");
if (charCode == 0) {
int precCharCode = Integer.valueOf(in.charAt(charAt - 1) + "");
if (precCharCode == 1)
charCode = 10;
if (precCharCode == 2)
charCode = 20;
}
char curChar = numberToChar.get(charCode);
result.addAll(decodeHelper(numberToChar, in, charAt + 1, arrayList));
arrayList.remove(arrayList.size() - 1);
if (in.length() > charAt + 1) {
charCode = Integer.valueOf(in.substring(charAt, charAt + 2));
if (charCode <= 26) {
curChar = numberToChar.get(charCode);
arrayList));
arrayList.remove(arrayList.size() - 1);
}
}
}
return result;
}
}

Output:
Please enter any digit number but combination of 1 to 26 .......
2010
All possible Alphabet codes for the give Number: 2010
taj
baj
btj
tj
btaj

Comment hidden because of low score. Click to expand.
0

Can you explain how the code baj is generated?

Comment hidden because of low score. Click to expand.
0

Also, if we make the assumption that the string contains zeros, then the code should handle cases like 20010. The code above doesn't.

Comment hidden because of low score. Click to expand.
3
of 3 vote

Non recursive Java code:

``````import java.util.ArrayList;
import java.util.List;

public class Alphabet {

/**
* @param args
*/
public static void main(String[] args) {

List<String> codes = findAllCodes("110203");

System.out.println(codes.size());
for (String code : codes){
System.out.println(code);
}
}

private static List<String> findAllCodes(String string) {

List<String> ret = new ArrayList<String>();
List<String> preRet = new ArrayList<String>();

for (int index = 0; index < string.length(); index ++){
List<String> temp1 = new ArrayList<String>();
List<String> temp2 = new ArrayList<String>();
if (index >=  1){
int val = Integer.valueOf(string.substring(index - 1, index + 1));
if (val <= 26 && val >= 10){
char chr = (char)(val + 96);
}
}
int val = Integer.valueOf(string.substring(index, index + 1));
if (val != 0){
char chr = (char)(val + 96);
}
preRet = ret;
ret = temp1;
}
return ret;
}

private static List<String> addChrToPrefix(List<String> preRet, char chr) {

List<String> ret = new ArrayList<String>();
if (preRet.size() == 0){
}
for (String item : preRet){
}
return ret;
}

}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Yeah, so you can recursively solve the sub-problems and memoize the results using dynamic programming. In other words:

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int count_valid(char *str, int size, int *array) {
int n, count = 0;
char substr[2];
if (size == 0)
return 1;
if (size == 1) {
if (*str != '0')
return 1;
else return 0;
}
if (array[size] >= 0)
return array[size];

if (str[size-1] != '0')
count += count_valid(str, size-1, array);

strncpy(substr, str+(size-2), 2);
n = atoi (substr);
if (n >= 1 && n <= 26)
count += count_valid(str, size-2, array);

array[size] = count;
return count;
}

int main () {
char *input = "1234";
int i, size = strlen(input);
int *array = (int *) malloc (sizeof(int) * (size+1));
for (i=1; i <= size; i++)
array[i] = -1;

printf ("%d\n", count_valid(input, size, array));
}``````

Comment hidden because of low score. Click to expand.
0

I am getting only the value 3 as the output for different inputs.

Comment hidden because of low score. Click to expand.
0

That's right. Try with "123123".

Comment hidden because of low score. Click to expand.
0

Output for "123123" is 9 and rightly so.

Comment hidden because of low score. Click to expand.
0

This looks right. It is O(n) time and O(n) space.

I won't comment on the code though.

Comment hidden because of low score. Click to expand.
0

@Loler: anything wrong with the code/style? Feedback is most welcome.

Comment hidden because of low score. Click to expand.
0

Ok, since you asked here are a few comments, one major, on neither major nor minor and the rest minor/nitpicks.

1) Major objection: You are making the caller of count_valid be responsible for allocating and passing in the array. Leaky interface. Can lead to bugs/unmodular code, in fact, see point 2 below.

2) You are not freeing memory.
(You could argue that the program is exiting anyway, but then your program is not of much use then :-))

3) The use of substr, strncpy and atoi could _possibly_ end up pulling in unnecessary libs. (Perhaps not the case, but who knows).

4) You can get rid of the recursion: see one of the other answers which talks about a simple linear time algorithm, which is essentially the same (scan from left to right, instead of right to left), but is not recursive. Of course, your intent was probably to demonstrate recursion + memoization.

5) You are allocating an array of size+1 ( I suppose for cleaner count_valid) when you don't really need the extra byte, a potential sign that the code could be rewritten better. In fact if you try to get rid of the recursion, you will probably see that you will get clean code without this extra byte problem.

6) The use of -1 to denote unmemoized sub-problems (you have lost the ability to use an unsigned type there, for instance). You are in effect mixing data with metadata.

7) If this was C++ (which I am presuming not, hence minor comment), you are missing the const on str.

8) If this was C++, you don't need to declare i in main specifically. Scope it to the for loop. In fact the later C standards also support that I think.

The main problem is 1 (and to some extent 2), and the rest you can dismiss as nitpicks/irrelevant/wrong/clueless if you want.

Also, I do understand this was just a quick code to demonstrate what you were saying, but you asked for feedback :-)

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

f('101126') = 5, but get 8

or

f('101110') = 2, but get 3

Comment hidden because of low score. Click to expand.
0

``````if (size == 0)
return 1;``````

In this case, you are saying that an empty string has one interpretation, but I would argue that it has zero valid interpretations. Why do you return one interpretation here?

Comment hidden because of low score. Click to expand.
0

@Raffi: That is kind of the "base case". We need it for the recursion to work.

Comment hidden because of low score. Click to expand.
0

@chisingh you didn't use "array" ?
Is it for getting back all the combinations?If yes can you show how you plan to use it?

Comment hidden because of low score. Click to expand.
0

the purpose of 'array' is this:

``````if (array[size] >= 0)
return array[size];
.
.
.
array[size] = count;``````

Just to remember the results of subproblems, and not re-calculate them. You could do it in other ways also, as suggested by Loler.

Comment hidden because of low score. Click to expand.
1
of 1 vote

This has a simple linear time algorithm. say the string is given as an array a[1...n]

You maintain another array which maintains the valid counts of prefixes, count[k] = valid count of a[1...k].

Now you scan a from 1 to n.

When you are considering j, there two possible splits involving j which end a j:
"a[1...j-1]" :"a[j]" or "a[1...j-2]" : "a[j-1] a[j]"

Now all you need to do is add the relevant counts (already computed till j-1 in count array)

Comment hidden because of low score. Click to expand.
0

this is ok but how do you plan to write an algo for this?

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````def get_interpretations(string):
def get_branchs(string):
if not string or len(string) == 1:
return 0
if string[0:2] <= '26':
if '0' not in string[1:3]:
return 1 + get_branchs(string[1:]) + get_branchs(string[2:])
else:
return get_branchs(string[2:])
else:
return get_branchs(string[1:])
return 1 + get_branchs(string)``````

Comment hidden because of low score. Click to expand.
0

Time complexity of this would be horrible.

Comment hidden because of low score. Click to expand.
0

``````def memoize(f):
cache= {}
def memf(key):
if key not in cache:
cache[key] = f(key)
return cache[key]
return memf

def get_interpretations(string):
@memoize
def get_branchs(string):
if not string or len(string) == 1:
return 0
if string[0:2] <= '26':
if '0' not in string[1:3]:
return 1 + get_branchs(string[1:]) + get_branchs(string[2:])
else:
return get_branchs(string[2:])
else:
return get_branchs(string[1:])
return 1 + get_branchs(string)``````

Comment hidden because of low score. Click to expand.
0

Cool feature of python.

Comment hidden because of low score. Click to expand.
1
of 1 vote

The solution is more like fibonaci series
where there is a choice
F(n) = F(n-1)+F(n-2)
or F(n) = F(n-1)
and the condition is atoi(string[n-1] string[n] ) < 27

``````#include <iostream>
#include <cstring>
using namespace std;
int main()
{
char * input ="1234";
int size = strlen(input);
int prev_val=0,curr_val=0,prev_prev_val=1;
for(int i=0;i<size;i++)
{
if(i!=0)
{
if((int)(input[i-1])<2+48 || ((int)(input[i-1])==2+48 &&
(int)(input[i])<7+48))
curr_val = prev_val + prev_prev_val;
else
curr_val = prev_val;
}
else
{
curr_val = 1;
prev_val = 1;
}
prev_prev_val = prev_val;
prev_val = curr_val;
}
cout<<curr_val<<endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

Here is a simple code with recursion

``````#include<stdio.h>
#include<conio.h>
#include<string.h>
void generate_alphabets(char *num,char *str,int start,int depth)
{
if(start>=strlen(num))
{
printf("\n %s",str);
return;
}

str[depth]=(num[start]-'0'-1+97);
generate_alphabets(num,str,start+1,depth+1);
if(num[start+1])
{
int result=(num[start]-'0')*10+(num[start+1]-'0')-1;
if(result<=25)
str[depth]=result+97;
str[depth+1]='\0';

generate_alphabets(num,str,start+2,depth+1);

}

}
int main()
{
char str[50]={'\0'};
char num[10]="1123";
generate_alphabets(num,str,0,0);
}``````

Comment hidden because of low score. Click to expand.
0

It doesn't work for this input: "101523"

Output list cannot contain a. It must start with j since 10=a. But pretty close.

Comment hidden because of low score. Click to expand.
1
of 1 vote

@diffuser78 i have modified the code to handle such cases. Here it is. Also tell me if there is any other case i have missed in valid inputs (i have considered valid inputs only)

``````#include<stdio.h>
#include<conio.h>
#include<string.h>
void generate_alphabets(char *num,char *str,int start,int depth)
{
if(start>=strlen(num))
{
printf("\n %s",str);
return;
}

if(num[start+1]!='0')
{
str[depth]=(num[start]-'0'-1+97);
generate_alphabets(num,str,start+1,depth+1);
}

if(num[start+1])
{
int result=(num[start]-'0')*10+(num[start+1]-'0')-1;
if(result<=25)
{
str[depth]=result+97;
str[depth+1]='\0';

generate_alphabets(num,str,start+2,depth+1);
}

}

}
int main()
{
char str[50]={'\0'};
char num[10]="101523";
generate_alphabets(num,str,0,0);
}``````

Comment hidden because of low score. Click to expand.
0

Works like a charm for most cases except these. Still a pretty good job.

"110203"

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public class PrintStringsAccordingToNumber {
static String alphabet="#abcdefghijklmnopqrstuvwxyz";
public static void main(String[] args) {

parseNumber(0,3,"1123","");

}

private static void parseNumber(int i, int j, String string,String result) {
if(j<i){System.out.println(result); return;}

int c=Integer.parseInt(string.charAt(j)+"");
if(c<=26)parseNumber(i, j-1, string, alphabet.charAt(c)+result);

if(j>0){
c=Integer.parseInt(string.charAt(j-1)+""+string.charAt(j)+"");
if(c<=26)parseNumber(i, j-2, string, alphabet.charAt(c)+result);
}

}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

In python:

``````def combiner(x, p=[]):
if len(x) == 0:
c = list(filter(lambda i: 0 < i <= 26, p))
c = list(map(lambda i: chr(i+96), c))
print(''.join(c),' // ',''.join(map(lambda i: str(i),p)))
return
combiner(x[1:], p + x[0:1])
if len(p) != 0 and (p[-1] * 10) + x[0] <= 26:
combiner(x[1:],p[:-1] + [(p[-1] * 10) + x[0]])``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Generally, because there are some recomputations on the subproblems, we can use a hash map to store the sub solutions.
The recursive calls on each string are sometimes called twice(because there might be combination of two numbers which are possible to map to a char) , and combine the two sub solutions into one, and then return.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This has an O(n) time and O(1) space algorithm, by noting that there are locations where only one choice is possible, which causes "breaks" and valid counts for substrings without breaks are fibonacci numbers.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static int CountValid(string s)
{
int count = 0;
if (string.IsNullOrWhiteSpace(s)) return 0;
if (s.IndexOf('0') == -1)
count++; //one valid interpretation with all single digit numbers transformed to chars 'a' - 'i'
for (int i = 0; i < s.Length - 1; i++)
{
int twoCharInterpretation = GetInt(s, i);
if (twoCharInterpretation != 10 // since 10 can only have one interpretation => j
&& twoCharInterpretation != 20 // since 20 can only have one interpretation => t
&& twoCharInterpretation > 9 // 06 cannot be valid interpretation since it is either part of 10 or 20
&& twoCharInterpretation <= 26)
{
count++;
}
if (twoCharInterpretation % 10 == 0 && twoCharInterpretation > 26)
{
return 0;// like 11301 334508 are invalid 10, 20 can be valid, but 30 is not
}
}
return count;
}

private static int GetInt(string s, int index)
{
string twoChars = string.Empty;
twoChars = twoChars + s[index] + s[index + 1];
return int.Parse(twoChars);
}``````

Comment hidden because of low score. Click to expand.
0

It is failing in few cases.
for 1221 it is returning 4. But the answer is 5
abba,lba,ava,abu,lu

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>

#define CHAR_SIZE 26
#define PERMUTE_SIZE 1000

static char *permu[PERMUTE_SIZE]; /*Right now I am interested in only 3 chars */
static int k;

void swap(char *string, int i, int j)
{
char temp = string[i];
string[i] = string[j];
string[j] = temp;
}

void permute(char *string, int i, int n)
{
int j = 0;

if(i == n) {
permu[k] = malloc(strlen("1122"));
strcpy(permu[k], string);
k++;
} else {
for(j=i;j<=n;j++) {
swap(string, i, j);
permute(string, i+1, n);
swap(string, i, j);
}
}
}

int main()
{
int i, j, count = 0;
char a[CHAR_SIZE+1] = {0};
char *string = malloc(strlen("1122"));

strcpy(string, "1122");

/*let's permute now*/
permute(string, 0, strlen("1122")-1);

/*make hashtable*/
for(i=0;i<=CHAR_SIZE;i++)
a[i] = 'a' + i; /*TOD0:Take care of CAPS*/

for(i=0;i<k;i++) {
int decimal;
decimal = atoi(permu[i]);
//printf("string %d\n", decimal);
for(j=0;j<2;j++) {
if(decimal%100 > CHAR_SIZE){ /* take 2 elements */
decimal = decimal/100;
} else {
if(a[decimal%100 - 1] != -1) {
printf("%c", a[decimal%100 - 1]);
count++;
}
a[decimal%100 - 1] = -1;
decimal = decimal/100;
}
}
printf("\n");
}
printf("total count %d\n", count+strlen("1122"));
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````InterpretString(String oldstring,String remdigitsleft){

if (remdigitsleft==null){
if (oldstring.length!=0) system.out.println(oldstring);

return;
}

for (int i=0;i<remdigitsleft.length;i++){

String interpretchar=getInterpretchar(remdigitleft,i); //uptoni

if (interpretchar!=null){

vString(oldstring+interpretchar,remdigitsleft.substring(i+1,n-1))

}

}

}

//helping function
String getInterpretchar(String remdigitleft,int i){

string intptchar=Integer.parserInt(remdigitleft.substring(0,i+1));

switch(intptchar){

case 1: retunr 'A';break;

case 2: retunr 'B';break;
...................

...................
case 26: retunr 'Z';break;

}

}

This is the input function

InterpretString('','111');``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<cstdio>
#include<string>
#include<set>
#include<vector>
#include<iostream>
#include<cstdlib>

using namespace std;

set< vector<char> > sequence(string s, int start, int end){
set< vector<char> > output;
if (start > end){
vector<char> seq;
output.insert(seq);
}else if (start == end){
vector<char> seq;
char singleChar[1];
singleChar[0] = s[start];
int singleDigit = atoi(singleChar);
seq.push_back(char ( 'a' - 1 + singleDigit));
output.insert(seq);
}else{
set <vector<char> > sub_output = sequence(s, start+1, end);
set <vector<char> >::iterator it = sub_output.begin();
char singleChar[1]; singleChar[0] = s[start];
char zero[1]; zero[0] = '0';
int singleDigit = atoi(singleChar);
char charFromSingleDigit = (char) ('a' - 1 + singleDigit);
for (; it != sub_output.end(); ++it){
vector<char> sub_v = (*it);
sub_v.push_back(charFromSingleDigit);
output.insert(sub_v);
}
char bothChars[2];
bothChars[0] = s[start];
bothChars[1] = s[start+1];
int bothDigits = atoi(bothChars) - atoi(zero);
if (bothDigits <= 26){
char charFromBothDigits = (char) ('a' - 1 + bothDigits);
sub_output = sequence(s, start+2, end);
it = sub_output.begin();
for (; it != sub_output.end(); ++it){
vector<char> sub_v = *it;
sub_v.push_back(charFromBothDigits);
output.insert(sub_v);
}
}
}
return output;
}

int main(){
string s;
cin >> s;
cout << "Input string is: " << s << endl;
set< vector<char> > output = sequence(s, 0, s.length()-1);
set< vector<char> >::iterator it = output.begin();
for (; it != output.end(); ++it){
for (int i = 0; i< ((*it).size()); ++i){
printf("%c", ((*it)[i]));
}
printf("\n");
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0

And in linear time:

``````#include<cstdio>
#include<string>
#include<set>
#include<vector>
#include<iostream>
#include<cstdlib>

using namespace std;

set< vector<char> > sequence(string s, int start, int end, vector<set<vector<char> > >& allSets){
if (start > end){
set<vector<char> > output;
vector<char> seq;
output.insert(seq);
return output;
}else if (start == end){
if (allSets[start].empty()){
vector<char> seq;
char singleChar[1];
singleChar[0] = s[start];
int singleDigit = atoi(singleChar);
seq.push_back(char ( 'a' - 1 + singleDigit));
allSets[start].insert(seq);
}
return allSets[start];
}else{
if (allSets[start].empty()){
set <vector<char> > sub_output = sequence(s, start+1, end, allSets);
set <vector<char> >::iterator it = sub_output.begin();
char singleChar[1]; singleChar[0] = s[start];
char zero[1]; zero[0] = '0';
int singleDigit = atoi(singleChar);
char charFromSingleDigit = (char) ('a' - 1 + singleDigit);
for (; it != sub_output.end(); ++it){
vector<char> sub_v = (*it);
sub_v.push_back(charFromSingleDigit);
allSets[start].insert(sub_v);
}
char bothChars[2];
bothChars[0] = s[start];
bothChars[1] = s[start+1];
int bothDigits = atoi(bothChars) - atoi(zero);
if (bothDigits <= 26){
char charFromBothDigits = (char) ('a' - 1 + bothDigits);
sub_output = sequence(s, start+2, end, allSets);
it = sub_output.begin();
for (; it != sub_output.end(); ++it){
vector<char> sub_v = *it;
sub_v.push_back(charFromBothDigits);
allSets[start].insert(sub_v);
}
}
}
return allSets[start];
}
}

int main(){
string s;
cin >> s;
cout << "Input string is: " << s << endl;
set< vector<char> > output;
vector< set < vector<char> > > allSets; allSets.resize(s.length());
output = sequence(s, 0, s.length()-1, allSets);
set< vector<char> >::iterator it = output.begin();
for (; it != output.end(); ++it){
for (int i = 0; i< ((*it).size()); ++i){
printf("%c", ((*it)[i]));
}
printf("\n");
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

Your company has got a project for developing a software system. A similar software system was developed in your previous company. You discover that your company's interpretation of requirements is different from the interpretation taken by your previous company. Cost of project will tremendously increase if ambiguities in requirements are not resolved. You have also an ethical responsibility of confidentiality to your previous company. Discuss what you should do in such a situation? :please help me in this topic and give me the answer solution because i am a juniour student of computer science

Comment hidden because of low score. Click to expand.
0
of 0 vote

char arr[]={'-','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'};

public void method2(String till,int numbers[],int from){
if(from==numbers.length){
System.out.println(till);
return ;
}
char c=arr[numbers[from]];
method(till+c,numbers,from+1);

if((from<numbers.length-1)&&(numbers[from]*10+numbers[from+1])<=26){
method(till+arr[numbers[from]*10+numbers[from+1]], numbers, from+2);

}

}
public static void main(String args[]){
stringval sv=new stringval();
int num[]={1,2,1,1};
sv.method2("",num,0);

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Dynamic programming solution. O(n) time, O(n) space, can be optimized to O(1) space by just remembering the previous two values in the array.

``````var text = "262626";

var combinations = new Array(text.length);
combinations[0] = 1;
for (var i = 1; i <= text.length; i++) {
var currentCharacter = text.substr(i - 1, 1);
var previousCharacter = (i > 1) ? text.substr(i - 2, 1) : null;

combinations[i] = 0;

if (currentCharacter != '0') combinations[i] += combinations[i-1];
if ((previousCharacter !== null) && (previousCharacter !== '0') && (parseInt(previousCharacter + currentCharacter) <= 26)) combinations[i] += combinations[i-2];
}

console.log(combinations[text.length]);``````

Comment hidden because of low score. Click to expand.
0

Good observation.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<cstring>
using namespace std;
static int i=0;
int numberstring(char*);
int main()
{
char s[100];
cin>>s;
if((s==NULL)||(strlen(s)==0)) return 0;
else {i++;numberstring(s);}
cout<<"number of strings "<<i<<endl;
}
int numberstring(char* s)
{
if((strlen(s))>1)
{
if((*s-'0')>2) numberstring(++s);
else {
char *t=s;t++;
if(((*s-'0')==2)&&((*t-'0')>6)) numberstring(t);
else {
i++;
if ((*t-'0')==0) { i--; if(strlen(t)>1) numberstring(++t);}
else { if(strlen(t)>1) {char *r=t; if(*++r=='0') i--;numberstring(t);} }
}
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(1) space and time:

``````int interpretations(String str)
{
int index = str.length() - 1;
int count = 1;
int prevCount = 1, prevPrevCount = 1;
for (int i=index; i>=0; --i)
{
if (i < index)
{
int number = str.charAt(i + 1) - '0' + (str.charAt(i) - '0') * 10;
if (number <= 26)
{
count += prevPrevCount;
}
}
prevPrevCount = prevCount;
prevCount = count;
}
return count;
}``````

Comment hidden because of low score. Click to expand.
0

Could you please explain how this code works?

Comment hidden because of low score. Click to expand.
0
of 0 vote

{
{
public static void GetInterpretationCount(int[] l)
{
}

static void AddChild(Node n, int pos, int[] l)
{
if (pos < l.Length)
{
char y = (char)(l[pos] + 64);
n.left = new Node(y);
if (pos + 1 < l.Length)
{
int x = l[pos] * 10 + l[pos + 1];
if (x <= 26)
{
n.right = new Node((char)(x + 64));
}
}
}
}
{
int x = 0; int y = 0;
{
}
{
}
{
return 1;
}
return x + y;
}
}
class Node
{
public Node()
{
}
public Node(char x)
{
c = x;
}
public char c;
public Node left;
public Node right;
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

My code in C, linear time and space

``````#include<stdio.h>
#define MAX_SIZE 100 //Maximum input size

//returns true if current number be coupled with previous
inline int couple(int i, char inp[MAX_SIZE+1])
{
if(i<1)
return 0;
if(inp[i-1] == '1')
return 1;
if(inp[i-1] == '2' && inp[i] < '7')
return 1;
return 0;
}

//calculate number of ways
int calculate(char inp[MAX_SIZE+1])
{
int a1 = 1, a2=1, a3=1;
int i;
for(i=0; inp[i]!='\0'; i++){
if(couple(i, inp))
a1 = a2 + a3;
else
a1 = a2;
a3 = a2;
a2 = a1;
}
return a1;
}

int main(void)
{
char inp[MAX_SIZE+1];
scanf("%s", inp);
printf("%d\n", calculate(inp));
}

int calculate(char inp[MAX_SIZE], int size)
{
int a_n3 = 1, a_n1=1, a_n2=0;
int i;
for(int i=0; i<size; i++){
if(couple(i, inp, size))
a_n3 = a_n1 + a_n2;
else
a_n3 = a_n1;
a_n1 = a_n2;
a_n2 = a_n3;
}
return a_n3;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

let us do it recursively.please correct me if I am wrong
a[0...n-1] now add a[n].then let A(n-1) be the number of valid interpretations.then A(n)=A(n-1)+A(n-2) if a[n-1]<3 else A(n-1)+1.Hence we can do it by dynamic programming

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static int CountOfValidInterpretations(String input) {
return countLeafNodes(createSuffixTree(input));
}

static class Node {
int valid = 1;
Node right = null;
Node left = null;
}

private static int countLeafNodes(Node root) {
if (root == null)
return 0;
else {
int child = countLeafNodes(root.left) + countLeafNodes(root.right);
if (child == 0 && root.valid == 1)
return 1;
return child;
}
}

static Node createSuffixTree(String input) {
if (input.length() == 0) {
Node root = new Node();
return root;
} else if (input.length() == 1) {
Node root = new Node();
root.left = createSuffixTree(input.substring(1));
if (input.substring(0, 1).equalsIgnoreCase("0")) {
root.valid = 0;
root.left.valid = 0;
}
return root;
} else {
if (input.substring(0, 1).equalsIgnoreCase("1")) {
Node root = new Node();
if (!input.substring(1, 2).equalsIgnoreCase("0"))
root.left = createSuffixTree(input.substring(1));
root.right = createSuffixTree(input.substring(2));
return root;
} else if (input.substring(0, 1).equalsIgnoreCase("2")) {
Node root = new Node();
if (!input.substring(1, 2).equalsIgnoreCase("0")
&& !input.substring(1, 2).equalsIgnoreCase("7")
&& !input.substring(1, 2).equalsIgnoreCase("8")
&& !input.substring(1, 2).equalsIgnoreCase("9"))
root.left = createSuffixTree(input.substring(1));
root.right = createSuffixTree(input.substring(2));
return root;
} else {
Node root = new Node();
root.left = createSuffixTree(input.substring(1));
return root;
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

I think the problem can be solved recursively as stated previously and also iteratively. Iterative version is presumably tough to do.

Full implementation of recursive method in java is given below.

``````package org.murali.algos;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.regex.Pattern;

public class StringCodes {

static String input;
static String[] codes = { "", "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" };
static Set<String> strings = new HashSet<String>();

private static void printCodes(String input, String output) {

if (input != null) {

int len = input.length();

if (len == 0) {
} else if (len == 1) {
} else {
if (Integer.parseInt(input.substring(1, 2)) != 0)
printCodes(
input.substring(1),
output
+ codes[Integer.parseInt(input.substring(0,
1))]);

if (Integer.parseInt(input.substring(0, 2)) < 27)
printCodes(
input.substring(2),
output
+ codes[Integer.parseInt(input.substring(0,
2))]);
}
}
}

public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Pattern pattern = Pattern.compile(System.getProperty("line.separator"));
scanner.useDelimiter(pattern);

if (scanner.hasNextLine()) {
input = scanner.next();
}
Integer.parseInt(input);
printCodes(input, "");
System.out.println(strings);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Below is the code using Iterative approach.

1. Find all combinations sum to string length using 1's & 2's
2. Find possible words for each combination

``````import java.util.ArrayList;

public class StringAlgorithms {

public static ArrayList<String> getPossibleWords(String str) {
ArrayList<ArrayList<Integer>> combinations = getLengthCombinations(str.length());
ArrayList<String> result = new ArrayList<String>();
String letters = " abcdefghijklmnopqrstuvwxyz";
for (ArrayList<Integer> list : combinations) {
int lastPos = 0;
String currentWord = "";
boolean found = true;
for (Integer count : list) {
String s = str.substring(lastPos, lastPos + count);
int letterPosition = Integer.parseInt(s);
if (letterPosition >= letters.length()) {
found = false;
break;
}
currentWord += letters.charAt(letterPosition);
lastPos += count;
}
}
return result;
}

private static ArrayList<ArrayList<Integer>> getLengthCombinations(int n) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i <= n / 2; i++) {
ArrayList<Integer> value = new ArrayList<Integer>();
for (int j = 0; j < n - 2 * i; j++) value.add(1);
for (int j = 0; j < i; j++) value.add(2);
while (value != null) {
value = getNextCombination(value);
}
}
return result;
}

private static ArrayList<Integer> getNextCombination(ArrayList<Integer> values) {
int i;
ArrayList<Integer> result = new ArrayList<Integer>();
for (i = values.size() - 2; i >= 0; i--) {
if (values.get(i) == 1 && values.get(i + 1) == 2) break;
}
if (i == -1) return null;
swap(result, i, i + 1);
sortElements(result, i + 1, result.size() - 1);
return result;
}

private static void sortElements(ArrayList<Integer> values, int start, int end) {
for (int i = start; i < end; i++) {
for (int j = i + 1; j <= end; j++) {
if (values.get(i) > values.get(j)) {
swap(values, i, j);
}
}
}
}

private static void swap(ArrayList<Integer> array, int i, int j) {
int temp = array.get(i);
array.set(i, array.get(j));
array.set(j, temp);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def computeCombos(x):
def codeToChar(x):
return chr(ord('a') + x - 1)

def numToArray(x):
result = []
while x > 0:
result.append(x % 10)
x /= 10

result.reverse()
return result

def yieldCombo(digits):
if not digits:
yield []
return
if digits[0] > 2:
for i in yieldCombo(digits[1:]):
yield [digits[0]] + i
elif digits[0] == 2:
if len(digits) > 1:
if digits[1] == 0:
for i in yieldCombo(digits[2:]):
yield [20] + i
else:
for i in yieldCombo(digits[1:]):
yield [2] + i
if digits[1] < 7:
for i in yieldCombo(digits[2:]):
yield [20 + digits[1]] + i
else:
yield [2]
else:
if len(digits) > 1:
if digits[1] == 0:
for i in yieldCombo(digits[2:]):
yield [10] + i
else:
for i in yieldCombo(digits[1:]):
yield [1] + i
for i in yieldCombo(digits[2:]):
yield [10 + digits[1]] + i
else:
yield [1]

return [''.join([codeToChar(i) for i in entry])
for entry in yieldCombo(numToArray(x))]

print computeCombos(1123)
print computeCombos(1023)
print computeCombos(1120)
print computeCombos(1129)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````listString = list()

def getChar(num):
if  num >= 1 and num <= 26:
return chr(num + 96)
return ''

def getNum(char):
return ord(char) - 96

def generateStrings(numString, length):

newNum = int(numString[length-1])
if length == 1:
listString.append(getChar(newNum))
return

generateStrings(numString, length - 1)

# Check if the new number can be summed with the existing number
for i in range(len(listString)):

string =  listString[i]
newChar = getChar(newNum + getNum(string[-1])*10)
if newChar:
if newNum != 0:
listString.append(string[:-1] + newChar)
else:
listString[i] =	string[:-1] + newChar
if newNum != 0:
listString[i] =  string + getChar(newNum)

x = "1123"
x = "101523"
x = "1020"
generateStrings(x, len(x))``````

o/p =
1> ['aabc', 'kbc', 'alc', 'aaw', 'kw']
2> ['jaebc', 'jobc', 'jaew', 'jow']
3> ['jt']

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class GenerateCode{
private static char getCharacterForValue(int n) {
return (char)('A' + n - 1);
}
private static boolean isValidOneLengthString(String s) {
return Integer.parseInt(s) > 0;
}
private static boolean isValidTwoLengthString(String s) {
int val = Integer.parseInt(s);
return val > 9 && val < 27;
}
private static void generate(String prefix, String input) {
if (input.length() == 0) {
System.out.println(prefix);
return;
}
if (isValidOneLengthString(input.substring(0, 1))) {
generate(prefix + getCharacterForValue(Integer.parseInt(input.substring(0, 1))), input.substring(1));
}
if (input.length() > 1 && isValidTwoLengthString(input.substring(0, 2))) {
generate(prefix + getCharacterForValue(Integer.parseInt(input.substring(0, 2))), input.substring(2));
}
}
public static void main(String[] args){
generate("", "1123");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.*;
public class face
{      private static int count=0;
private static char ar[]=               {'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'};
static void  print_word(String str,String str1,int l,int i)
{
if(i>(l-1))
{
System.out.println(str1);
System.out.println("\n");
count++;
return;
}

int a=(int) (str.charAt(i));
print_word(str,str1 + ar[a-1-48],l,i+1);

if((l-1-i) >= 1)
{
int b= (int) (str.charAt(i+1));
b=b-48;
b= (a-48)*10 + b;

if(b<=26)
print_word(str,str1 + ar[b-1],l,i+2);

}

}

public static void main(String args[]) throws IOException

{

String str,str1;
str="1123";
str1="";

int l=str.length();
int i=0;
print_word(str,str1,l,i);
System.out.println(count);

}

}``````

Comment hidden because of low score. Click to expand.
0

there is no need to use hashmap we can simply use recursion by taking one and two char if possible and print it.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````string res;
void possibletext(char* input)
{
if (input == nullptr ||
input[0] == '\0')
{
cout<<res<<endl;
return;
}

// read first digit and print
if (input[0] >='1' && input[0] <='9' && input[1] != '0')
{
int num = (input[0] - '0') - 1;
res += ('a'+num);
possibletext(input+1);
res.pop_back();
}

// handle the special case where two digits can be combined
if (input[0] == '1' ||
(input[0] == '2' && input[1] >= '1' && input[1] <='6'))
{
int num = (input[0]-'0')*10 + (input[1]-'0') - 1;
res += (char)('a'+num);
possibletext(input+2);
res.pop_back();
}
}
int main(int argc, char** argv)
{
char* one = "1123";
possibletext(one);
_getch();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

For any query mail me at sahilkb23@gmail.com
This code was compiled using Dev-Cpp

``````#include<iostream.h>
#include<conio.h>

char code[] = " ABCDEFGHIGKLMNOPQRSTUVWXYZ";
char array[100];

void charcodes(char *arr,int &count,int p = 0)
{
int i;
if(*arr == 0)
{cout<<array<<endl; count++; return;}
i = (*arr)-'0';
array[p] = code[i];
array[p+1] = 0;
charcodes(arr+1,count,p+1);
i = i*10;
if(*(arr+1) != 0 ){
i += (*(arr+1))-'0';
if (i<=26)
{
array[p] = code[i];
array[p+1] = 0;
charcodes(arr+2,count,p+1);
}
}
}

int main()
{
int count;
char arr[100];
cout<<"Enter the String : ";
cin>>arr;
count = 0;
charcodes(arr,count);
cout<<endl<<"Count is : "<<count;
getch();
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

using namespace std;

void print(int n[],char s[],int nn,int ns,int num)
{
if(nn==num)
{
s[ns]='\0';
cout<<"\n"<<s;
return;
}
if(n[nn]==0)
{
print(n,s,nn+1,ns,num);
return;
}
s[ns]=(char)(n[nn]+64);
print(n,s,nn+1,ns+1,num);
if(ns<num-1)
{
int a=n[nn]*10+n[nn+1];
if(a<=26)
{
s[ns]=(char)(a+64);
print(n,s,nn+2,ns+1,num);
}
}
}
int main()
{
int n[]={1,1,0,2,0,3};
int size=sizeof(n)/sizeof(int);
char *s=new char[size+5];
print(n,s,0,0,size);
return 0;
}

Comment hidden because of low score. Click to expand.
0

good one works for all case

Comment hidden because of low score. Click to expand.
0
of 0 vote

Javascript Solution

{{
function getLetterRankWords(str) {
var letterRanks = {};
var alphabet = 'abcdefghijklmnopqrstuvwxyz';
for (var i = 0; i < alphabet.length; i++) {
letterRanks[ i+1 ] = alphabet[i];
}

var results = {};

var gobbleString = function(str, remainingStr, posToConsider) {
if (remainingStr === "") {
results[str] = true;
return;
}

if (posToConsider === 2 && remainingStr.length >= 2) {
// Consider the next two numbers
var nextTwoNum = parseInt( remainingStr[0] + remainingStr[1], 10 );
var letter = letterRanks[ nextTwoNum ];
if (letter) {
gobbleString(str + letter, remainingStr.substring(2), 1);
if (remainingStr.length >= 2) {
gobbleString(str + letter, remainingStr.substring(2), 2);
}
}
} else {
var letter = letterRanks[ parseInt(remainingStr[0], 10) ];
if (letter) {
gobbleString(str + letter, remainingStr.substring(1), 1);
if (remainingStr.length >= 2) {
gobbleString(str + letter, remainingStr.substring(1), 2);
}
}
}
}

gobbleString("", str, 1);
if (str.length >= 2) {
gobbleString("", str, 2);
}

return Object.keys(results);
}
getLetterRankWords('1123');
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static void getTranslation(String str, int cursor, String current)
{
if (str.length() == cursor)
{
System.out.println(current);
return;
}

int one = Integer.parseInt(str.substring(cursor, cursor+1));
if (one >0 && one <=26)
{
getTranslation(str, cursor+1, current + getChar(one));
}

int two = cursor+1 < str.length() ? Integer.parseInt(str.substring(cursor, cursor+2)):-1;
if (two >0 && two <= 26)
{
getTranslation(str, cursor+2, current + getChar(two));
}
}

private static char getChar(int num)
{
int a = 'a'-1;

return (char) (num+a);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

f (n) = f(n-1) {if a[n] is not zero} + f(n-2) {if a[n-1]*10+a[n] <= 26} [f denotes no of ways]
1. Take two vectors v1 , v2
2. append a[0] to v1
3. i = 1
4. if a[i] is not zero, append a[i] to v1, else clear vector v1
5. if (b = a[i-1]*10+a[i]) <= 26 && >= 10, append b to v2; else clear vector v2
6. swap v1 & v2
7. i++, repeat step 4 till end
8. return v1 union v2

Comment hidden because of low score. Click to expand.
0
of 0 vote

my solution. Maybe is a duplicate of other people's solution.

``````#include <iostream>

using namespace std;

void genStr(string& str, int begin, string &output, int output_index, int &count)
{
if(begin >= str.size()) {
output[output_index] = '\0';
cout << output << endl;
count++;
return;
}

if(str[begin] == '0') { //skip
genStr(str, begin+1, output, output_index, count);
} else {
//use 1 digit
{
output[output_index] = str[begin]-'0'+'A'-1;
genStr(str, begin+1, output, output_index+1, count);
}

//use 2 digits
if(begin+1 < str.size()) {
int n = (str[begin]-'0')*10 + str[begin+1]-'0';
if(n <= 26) {
output[output_index] = n+'A'-1;
genStr(str, begin+2, output, output_index+1, count) ;
}
}
}
}

int genStr(string str) {
int count = 0;
string output;
output.resize(str.size()+1);

genStr(str, 0, output, 0, count);

return count;
}

int main()
{
int count  = 0;

//ABCDE  FGHIJ(10)
//KLMNO  PQRST
//UVWXY  Z
count  = genStr("1123");
cout << count << endl;

count = genStr("101523");
cout << count << endl;

count = genStr("110203");
cout << count << endl;

//  cout << "Hello World" << endl;

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution using backtracking:

#include <stdio.h>

void print(int N, char *s, int i)
{
int j;
if (N == 0)
{
for(j=(i-1);j>=0;j--)
{
printf("%c",s[j]);
}
printf("\n");
}
else
{
s[i] = 96 + N % 10;
i++;
print(N/10, s, i);
i--;

if ((N % 100 > 9) && (N % 100 <= 26))
{
s[i] = 96 + N % 100;
i++;
print(N/100, s, i);
}
}
}

int main()
{
int N;
char s[100];
scanf("%d",&N);
print(N,s,0);
return 0;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````string = "110203"

codes = [ chr(ord('a') + i) for i in range(0, 26) ]

def find_codes(num, code=[]):
if len(num) == 0:
try:
print ''.join([ codes[int(char) - 1] for char in code ])
except:
pass
else:
if num[0] != '0':
find_codes(num[1:], code[:] + [num[0]])

if len(num) > 1:
find_codes(num[2:], code[:] + [num[:2]])

find_codes(string)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution is based on the creation of a binary tree, left branch values smaller than the node, right branch values greater than the node and smaller than 26. A visitor then will visit the tree and create all the strings based on the path.

``````/**
* If a=1, b=2, c=3,....z=26. Given a string,
* find all possible codes that string can generate.
* Give a count as well as print the strings.
*
* For example:
* Input: "1123". You need to general all valid alphabet codes from this string.
*
* Output List
* aabc //a = 1, a = 1, b = 2, c = 3
* kbc // since k is 11, b = 2, c= 3
* alc // a = 1, l = 12, c = 3
* aaw // a= 1, a =1, w= 23
* kw // k = 11, w = 23
*
* @author patrick
*
*/
public class App {

private static final String DEFAULT = "1123";

public static void main(String[] args) {
char[] word = DEFAULT.toCharArray();

WordNode root = new WordNode(-1);

parse(word, 0, root);

PrintWordVisitor v = new PrintWordVisitor();
v.visit(root);

WordVisitor wv = new WordVisitor();
wv.visit(root);

for(String s : wv.getValues()) {
System.out.println(s);
}

}

private static void parse(char[] word, int index, WordNode parent) {
if(index<word.length) {
//build left node
int lvalue = Integer.parseInt(new String(new char[] {word[index]}));
WordNode left = new WordNode(lvalue);
parent.setLeft(left);

parse(word, index+1, left);

int rightIndex = index+1;
if(rightIndex<word.length) {
int rvalue = Integer.parseInt(new String(new char[] {word[index], word[rightIndex]}));
if(rvalue<=26) {
WordNode right = new WordNode(rvalue);
parent.setRight(right);

parse(word, rightIndex+1, right);
}
}
}

}

}``````

``````public class WordNode {

private WordNode left;
private WordNode right;

private int value;

public WordNode(int value) {
this.value = value;
}

public WordNode getLeft() {
return left;
}

public void setLeft(WordNode left) {
this.left = left;
}

public WordNode getRight() {
return right;
}

public void setRight(WordNode right) {
this.right = right;
}

public int getValue() {
return value;
}

public void setValue(int value) {
this.value = value;
}

}``````

Visitor that print all the possible strings:

``````public class WordVisitor {

private static int BASE_VALUE = 96;

private Set<String> values = new HashSet<String>();

public void visit(WordNode node) {
values.clear();
visitHelper("", node);
}

private void visitHelper(String base, WordNode node) {
if(node.getValue()>0) {
base += new String(Character.toChars(BASE_VALUE+node.getValue()));
}
//is leaf?
if(node.getLeft() == null) {
}
else {
visitHelper(base, node.getLeft());
if(node.getRight() != null) {
visitHelper(base, node.getRight());
}
}
}

public Set<String> getValues() {
return values;
}

}``````

Here is another visitor that print the tree structure:

``````public class PrintWordVisitor implements IVisitor {

public void visit(WordNode node) {
visitHelper("", node);
}

private void visitHelper(String indent, WordNode node) {
System.out.println(indent + "[node: " + node.getValue() + "]");
if(node.getLeft() != null) {
visitHelper(indent+"  ", node.getLeft());
if(node.getRight() != null) {
visitHelper(indent+"  ", node.getRight());
}
}
}
}``````

Output:

``````Tree structure:
[node: -1] // Root
[node: 1]
[node: 1]
[node: 2]
[node: 3]
[node: 23]
[node: 12]
[node: 3]
[node: 11]
[node: 2]
[node: 3]
[node: 23]

String combinations:

kw
kbc
alc
aaw
aabc``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace printAllCombo
{
class Program
{
static void printCombo(string input,int index,string stringToPrint,int tempIndex)
{
if (tempIndex == input.Length-1)
{
Console.WriteLine("String:"+stringToPrint);
return;
}
for (int i = index; i < input.Length; i++)
{

int temp=int.Parse(input.Substring(index, i-index+1));
if (i + 1 < input.Length && input[i + 1] == '0')
{if((temp*10)>=1 && (temp*10)<=26)
{
i++;
printCombo(input, i + 1, stringToPrint + (char)((temp*10) + 'a' - 1), i);
}
}
else
{
if (temp >= 1 && temp <= 26)
{
printCombo(input, i + 1, stringToPrint + (char)(temp + 'a' - 1), i);
}
}
}
}
static void Main(string[] args)
{

printCombo("110203", 0, "", 0);
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <iostream>
#include <string>
#include <sstream>

using namespace std;

class alphaCodes {

int convertToInt(string s);
bool isValidLetter(int n);
void printCode(char* a, int k);
void backtrack(char* a, int k, string input, int s, int& count);

public:
void printAllCodes(string input);
char getLetter(int n);

};

void alphaCodes::printAllCodes(string input) {
char* a = new char[input.length() + 1];
int k = 0;
int s = 0;
int count = 0;
backtrack(a, k, input, s, count);
cout << "Count:" << count << endl;
}

int alphaCodes::convertToInt(string s){
int val;
istringstream ( s ) >> val;
return val;
}

char alphaCodes::getLetter(int n) {
return (n-1) + 'a';
}

bool alphaCodes::isValidLetter(int n) {
return (n > 0 && n < 27);
}

void alphaCodes::printCode(char* a, int k){
for (int i=0; i < k; ++i){
cout << a[i];
}
cout << endl;
}

void alphaCodes::backtrack(char* a, int k, string input, int s, int& count) {
if(s == input.length()){
printCode(a, k);
count++;
}
else {

int n = convertToInt(input.substr(s, 1));
if(isValidLetter(n)){
a[k] = getLetter(n);
backtrack(a, k+1, input, s+1, count);
}
if(s+1 < input.length()){
n = convertToInt(input.substr(s,2));
if(isValidLetter(n)){
a[k] = getLetter(n);
backtrack(a, k+1, input, s+2, count);
}
}
}
}

int main(int argc, char** argv) {
if (argc < 2){
cout << "Please enter an input number string!" << endl;
return 0;
}
alphaCodes a;
a.printAllCodes(argv[1]);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

/// Just another recursive solution. Who know iterative solution? Plz show me.

``````int print_vec_char(vector<char> & one)
{
for(int i = 0; i < one.size(); i ++) printf("%c", one[i]);
printf("\n");
return 0;
}

int gen_string(string & s, int sel, vector<char> & one)
{
if(sel == s.size()) {
print_vec_char(one);
return 0;
}
if(s[sel] == '0') return 0;
/// 1.0 using one char
one.push_back(s[sel] - '1' + 'a');
gen_string(s, sel + 1, one);
one.pop_back();
/// 2.0 using two char
if(sel <= s.size() - 2) {
int t = (s[sel] - '0') * 10 + (s[sel+1] - '0');
if(t <= 26) {
one.push_back(t + 'a' - 1);
gen_string(s, sel + 2, one);
one.pop_back();
}
}

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/**
* If a=1, b=2, c=3,....z=26. Given a string,
* find all possible codes that string can generate.
* Give a count as well as print the strings.
*
* For example:
* Input: "1123". You need to general all valid alphabet codes from this string.
*
* Output List
* aabc //a = 1, a = 1, b = 2, c = 3
* kbc // since k is 11, b = 2, c= 3
* alc // a = 1, l = 12, c = 3
* aaw // a= 1, a =1, w= 23
* kw // k = 11, w = 23
*
* @author patrick
*
*/
public class Digit2String {

public static void main(String[] args) {
d2s("",new int[]{1, 1, 2, 3}, 0);
}

public static void d2s(String accumulator, int[] A, int start) {
if(start>=A.length) {
System.out.println(accumulator);
return;
}
d2s(accumulator + new String(d2c(A[start])), A, start+1);
if(start<A.length-1) {
int c2value= A[start]*10 + A[start+1];
if(c2value<=26)
d2s(accumulator + d2c(c2value), A, start+2);
}
}

private static String d2c(int v) {
return new String(Character.toChars(96+v));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Puzzle2
{
class Program
{
/*If a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.

For example:
Input: "1123". You need to general all valid alphabet codes from this string.

Output List
aabc //a = 1, a = 1, b = 2, c = 3
kbc // since k is 11, b = 2, c= 3
alc // a = 1, l = 12, c = 3
aaw // a= 1, a =1, w= 23
kw // k = 11, w = 23*/
public static Dictionary<int, char> map = new Dictionary<int,char>();
static void Main(string[] args)
{
for (int i = 1; i <= 26; i++)
{
map[i] = (char)('a' + (i - 1));
}
PrintCodes(string.Empty, "1123");
}

public static void PrintCodes(string codePrefix, string subString)
{
if(subString.Length==0)
Console.WriteLine(codePrefix);

for (int i = 1; i <= 2; i++)
{
if (i > subString.Length)
break;
else if (i == subString.Length)
Console.WriteLine(codePrefix + map[int.Parse(subString)].ToString());
else
{
string subSubString = subString.Substring(0, i);
string codePre = map[int.Parse(subSubString)].ToString();
PrintCodes(codePrefix + codePre, subString.Substring(i));
}

}
}
}
}
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Puzzle2
{
class Program
{
/*If a=1, b=2, c=3,....z=26. Given a string, find all possible codes that string can generate. Give a count as well as print the strings.

For example:
Input: "1123". You need to general all valid alphabet codes from this string.

Output List
aabc //a = 1, a = 1, b = 2, c = 3
kbc // since k is 11, b = 2, c= 3
alc // a = 1, l = 12, c = 3
aaw // a= 1, a =1, w= 23
kw // k = 11, w = 23*/
public static Dictionary<int, char> map = new Dictionary<int,char>();
static void Main(string[] args)
{
for (int i = 1; i <= 26; i++)
{
map[i] = (char)('a' + (i - 1));
}
PrintCodes(string.Empty, "1123");
}

public static void PrintCodes(string codePrefix, string subString)
{
if(subString.Length==0)
Console.WriteLine(codePrefix);

for (int i = 1; i <= 2; i++)
{
if (i > subString.Length)
break;
else if (i == subString.Length)
Console.WriteLine(codePrefix + map[int.Parse(subString)].ToString());
else
{
string subSubString =  subString.Substring(0, i);
string codePre = map[int.Parse(subSubString)].ToString();
PrintCodes(codePrefix + codePre, subString.Substring(i));
}

}
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````static class Solution{
public static void main(String[] args){
AllPossibleChars("","1123");
}

public static void AllPossibleChars(String prefix,String str){
if(str.length()==0){
System.out.println(prefix);
return;
}
char c = (char)(Integer.parseInt(str.substring(0,1))+96);
AllPossibleChars(prefix+c, str.substring(1));
if(str.length()>=2)
if(Integer.parseInt(str.substring(0,2))<=26){
c = (char)(Integer.parseInt(str.substring(0,2))+96);
AllPossibleChars(prefix+c, str.substring(2));
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>
#include<conio.h>
using namespace std;
#include<vector>
#include<map>
#include<iostream>
int main()
{
int i,j,k,t,y,m;
int a[100];
cout<<"enter the length of the number";
cin>>j;
for(i=0;i<j;i++)
{
cin>>a[i];
}
for(i=0;i<j;i++)
{
if(i==(j-1))
for(t=0;t<=i;t++)
cout<<(char)(a[t]+64)<<" ";
else
{
for(t=0;t<i;t++)
cout<<(char)(a[t]+64)<<" ";
for(k=i;k+1<j;k=k+2)
{
if(a[k]*10+a[k+1]<=26)
{

for(m=i;m<=k;m=m+2)
{
y=a[m]*10+a[m+1];
if(y<=26)
cout<<(char)(y+64)<<" ";
}
int l=k+2;
for(t=l;t<j;t++)
cout<<(char)(a[t]+64)<<" ";
}
else
{
for(m=i;m<=k;m=m+2)
{
y=a[m]*10+a[m+1];
if(y<=26)
cout<<(char)(y+64)<<" ";
else
{
cout<<(char)(a[m]+64)<<" ";
cout<<(char)(a[m+1]+64)<<" ";
}
}
int l=k+2;
for(t=l;t<j;t++)
cout<<(char)(a[t]+64)<<" ";
}
cout<<"\n";
}
}

}
getch();
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Its a simple backtracking question...here is my c++ code for it...

``````#include<iostream>
using namespace std;

void printstr(string num,string str,int n)
{
if(n<0)
{
cout<<str<<endl;
return ;
}

int temp;
string str1="",str2="";
temp=(num[n]-'0');
if(n>0)
{
temp+=(num[n-1]-'0')*10;
}

str1=(char)((temp%10)+'a'-1)+str;
printstr(num,str1,n-1);
if(temp>10 && temp<27)
{
str2=(char)(temp+'a'-1)+str;
printstr(num,str2,n-2);
}
}

int main()
{
string num,str="";
cout<<"enter the string "<<endl;
cin>>num;

printstr(num,str,num.length()-1);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import java.io.*;
import java.util.*;

public class PatternPrint {
public static ArrayList<String> str= new ArrayList<String>();
public static String input;
public static void main(String[] args) throws IOException, NullPointerException{
System.out.println("Give the input:");
getPatterns(input, "");
for(int i=0; i<str.size(); i++){
System.out.println(str.get(i));
}
}

public static void getPatterns(String inp, String ans) throws NullPointerException {
if(inp.length() == 0){
return;
}
getPatterns(inp.substring(1), ans+getString(inp.substring(0,1)));

if(inp.length()>=2){
String s2 = getString(inp.substring(0,2));
if(s2.equals("Error!"))
return;
getPatterns(inp.substring(2), ans+s2);
}
}
public static String getString(String s){
int n1 = Integer.parseInt(s);
char ch1 = (char) ('a'+n1-1);
if(n1>26)
return "Error!";
return Character.toString(ch1);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

My implementation in ruby

``````def print_streengs number

\$index = ('a'..'z').to_a

def consume(number,str = '')

# Consume 1 number
if number != nil
tmpstr = str.clone + \$index[number.to_s[0].to_i - 1]
tmpnumber = number.to_s.size == 1? nil : number.to_s[1..number.to_s.size-1]
consume(tmpnumber,tmpstr)
end

# Consume 2 numbers
if number != nil and number.to_s.size >= 2
tmpstr = str.clone + \$index[number.to_s[0,2].to_i - 1]
tmpnumber = number.to_s.size == 2? nil : number.to_s[2..number.to_s.size-1]
consume(tmpnumber,tmpstr)
end

# Print the number
if number == nil
puts str
end

end

consume(1123)

end

print_streengs 1123
#aabc
#aaw
#alc
#kbc
#kw
#``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<iostream>
#include<vector>
using namespace std;
int n;
vector<string> a[100];
void dfs(string s,int i,string x)
{
if(i>=n){cout<<x<<endl;return;}
int v=s[i]-'0';
char ch;
ch=v+'a'-1;
x.push_back(ch);
dfs(s,i+1,x);
if(i<n-1)
{
v=v*10+s[i+1]-'0';
if(v<=26)
{
ch=v+'a'-1;
x[x.size()-1]=ch;
dfs(s,i+2,x);
}
}
}
int main()
{
string s;
cin>>s;
n=s.size();
dfs(s,0,0);
cin>>s;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry !it should be dfs(s,0,x) instead of dfs(s,0,0) and x should be an empty string initialized in main()

Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple dfs implementation

``````#include<iostream>
#include<vector>
using namespace std;
int n;
vector<string> a[100];
void dfs(string s,int i,string x)
{
if(i>=n){cout<<x<<endl;return;}
int v=s[i]-'0';
char ch;
ch=v+'a'-1;
x.push_back(ch);
dfs(s,i+1,x);
if(i<n-1)
{
v=v*10+s[i+1]-'0';
if(v<=26)
{
ch=v+'a'-1;
x[x.size()-1]=ch;
dfs(s,i+2,x);
}
}
}
int main()
{
string s,x;
cin>>s;
n=s.size();
dfs(s,0,x);
cin>>s;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

DP, O(n), with python

``````def output(original, pre):

if len(original) == 0:
print pre
return
if len(original) == 1:
print pre + chr(96 + int(original))
return

if int(original[0:2]) < 27:
new_chr = chr(96 + int(original[0:2]))
output(original[2:], pre + new_chr)
new_chr = chr(96 + int(original[0:1]))
output(original[1:], pre + new_chr)

if __name__ == '__main__':
output('1123', '')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

A really simple recursive code in python:

str_list = []

def str_map(str1, f_str, i):
if i == len(str1):
str_list.append(f_str)

if i < len(str1):
t_str = list(f_str)
t_str.append(chr(96+int(str1[i])))

str_map(str1, t_str, i+1)

if i+1 < len(str1):
t1_str = list(f_str)
t1_str.append(chr(96+int(str1[i:i+2])))
str_map(str1, t1_str, i+2)

def test():
str1 = "1123"
str_map(str1, [], 0)
print str_list

test()

Comment hidden because of low score. Click to expand.
0
of 0 vote

Following code works on all inputs, even corner cases which include 0 in the input string. I have assumed that if more than two consecutive 0's occur in the input string, there is no valid interpretation of the given string since we do not have any character which maps to 0.

``````#include <iostream>
#include <string>
#include <vector>

using namespace std;

char toChar(char a)
{
return a-'0' + 'a' -1;
}
void gen(std::vector<char> str, string num)
{
if (num[0]=='0') return;

if (num.size()==0)
{
for (int i = 0; i < str.size(); ++i)
{
cout<<str[i];
}
cout<<endl;
return;
}

str.push_back(toChar(num[0]));
gen(str, num.substr(1));

if (num.size()>=2)
{
int next=num[1]-'0' + (num[0]-'0')*10;
if (next<=26)
{
str.pop_back();
str.push_back('a'+next-1);
gen(str, num.substr(2));
}
}
}

int main(int argc, char const *argv[])
{
std::vector<char> str;
string num("101523");
gen(str, num);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````bool validChar(char a,char b)
{
if(10*(a-'0')+(b-'0')<26)
return true;
return false;
}

void print(int i,string s,string p)
{
if(i==s.length())
{
cout<<p<<endl;
return;
}
if(s[i]=='0')
return;
print(i+1,s,p+(char)('a'+(s[i]-'0'-1)));
if(i+1<s.length() && validChar(s[i],s[i+1]))
print(i+2,s,p+(char)('a'-1+(10*(s[i]-'0')+(s[i+1]-'0'))));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````bool validChar(char a,char b)
{
if(10*(a-'0')+(b-'0')<26)
return true;
return false;
}

void print(int i,string s,string p)
{
if(i==s.length())
{
cout<<p<<endl;
return;
}
if(s[i]=='0')
return;
print(i+1,s,p+(char)('a'+(s[i]-'0'-1)));
if(i+1<s.length() && validChar(s[i],s[i+1]))
print(i+2,s,p+(char)('a'-1+(10*(s[i]-'0')+(s[i+1]-'0'))));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a python implementation

``````def decodable(num_string):
return int(num_string) > 0 and int(num_string) <= 26

def decode(num_string):
d = "abcdefghijklmnopqrstuvwxyz"
return d[int(num_string) - 1]

#return every way to decode a number into letters
def decode_num(num_string):
d = {}
d[0] = [decode(num_string[0])]
if len(num_string) == 1:
return d[0]
d[1] = [decode(num_string[0]) + decode(num_string[1])]
if decodable(num_string[:2]):
d[1].append(decode(num_string[:2]))
for i in range(2, len(num_string)):
d[i] = list()
for string in d[i-1]:
d[i].append(string + decode(num_string[i]))
for string in d[i-2]:
if decodable(num_string[i-1:i+1]):
d[i].append(string + decode(num_string[i-1:i+1]))
return d[len(num_string) - 1]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's my dynamic approach in python (repost after signing in)

``````def decodable(num_string):
return int(num_string) > 0 and int(num_string) <= 26

def decode(num_string):
d = "abcdefghijklmnopqrstuvwxyz"
return d[int(num_string) - 1]

#return every way to decode a number into letters
def decode_num(num_string):
d = {}

d[0] = []
if decodable(num_string[0]):
d[0] = [decode(num_string[0])]
if len(num_string) == 1:
return d[0]

d[1] = []
if decodable(num_string[0]) and decodable(num_string[1]):
d[1].append(decode(num_string[0]) + decode(num_string[1]))
if decodable(num_string[:2]):
d[1].append(decode(num_string[:2]))

for i in range(2, len(num_string)):
d[i] = list()
for string in d[i-1]:
if decodable(num_string[i]):
d[i].append(string + decode(num_string[i]))
for string in d[i-2]:
if decodable(num_string[i-1:i+1]):
d[i].append(string + decode(num_string[i-1:i+1]))
return d[len(num_string) - 1]``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````import string

LETTERS = string.lowercase
MAX_DIGITS = len(str(len(LETTERS)))

def to_letter(n):
n = int(n)
if n <= 0 or n > len(LETTERS):
return None
return LETTERS[n - 1]

def find_codes(input_str):
# Base case: a one-digit or zero-digit number is supplied
if len(input_str) == 0:
return []
elif len(input_str) == 1:
return [to_letter(input_str)]

result = []
# MAX_DIGITS == 2 -> xrange(1, 3) -> [1, 2]
for i in xrange(1, MAX_DIGITS + 1):
curr_letter = to_letter(input_str[0:i])
if curr_letter is None:
continue

sub_codes = find_codes(input_str[i:])
if len(sub_codes) == 0:
sub_codes = [""]
for sub_code in sub_codes:
result.append(curr_letter + sub_code)

return result

def print_codes(input_str):
result = find_codes(input_str)
print len(result)
print "\n".join(result)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>
#include <string.h>

void decodeString(char *input, char *solution, int startIndex, int indexInSolution) {
int size = strlen(input);
if (startIndex == size) {
solution[indexInSolution] = '\0';
printf("%s\n", solution);
return;
}
int value = input[startIndex] - '0';
solution[indexInSolution] = 'a' + value - 1;
startIndex++;
indexInSolution++;
decodeString(input, solution, startIndex, indexInSolution);

if ((startIndex < size) &&
(value == 1) ||
(value == 2 && input[startIndex] <= '6')) {
int nextValue = value * 10 + (input[startIndex] - '0');
solution[indexInSolution - 1] = 'a' + nextValue - 1;
decodeString(input, solution, startIndex + 1, indexInSolution);
}
}

int main(void) {
char string[256], result[256];

fgets(string, sizeof(string), stdin);
decodeString(string, result, 0, 0);

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

somebody please explain the algorithm to solve this problem rather than source code.

Comment hidden because of low score. Click to expand.
0
of 0 vote

somebody please explain the algorithm to solve it rather than the code

Comment hidden because of low score. Click to expand.
0

look up Depth First Search and watch some youtube videos about it. They will be a lot better than whatever i would write.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````//just implement "printL" method to print to the output of your choice

(function () {

var h = function (str, i, cach) {
if(cach[i]) return cach[i];

if(i === str.length) return [];

var r = [];
var cur, curH;
var j;
var k;
for (j = i+1; j < str.length+1 ; j++){
cur = parseInt(str.substring(i, j));
if(cur > 26) break;
cur = String.fromCharCode(96 + cur);//turn into char
curH = h(str, j, cach);
if(!curH.length) r.push(cur);
else{
for(k = 0; k < curH.length ; k++){
r.push(cur + curH[k]);
}
}
}
cach[i] = r;
return r;
};

var findCode = function (str) {
if(!str || !str.length) return [];
var cach = {};
return h(str, 0 , cach);
};

var printCode = function (str) {

var strArr = findCode(str);
var i;
for(i = 0; i < strArr.length ; i++){
printL(strArr[i]);
}
};

var test = function (str){
printCode(str);
};

var str = "1123";
test(str);

}())``````

Comment hidden because of low score. Click to expand.
0

Recursion + DP

Comment hidden because of low score. Click to expand.
0
of 0 vote

here my C++ solution:

``````const int alphabet_size = 26;

unordered_map<string, string> generate_char_ht() {
unordered_map<string, string> ht;
char char_A = 'a';

for (int i = 1; i <= alphabet_size; i++, char_A++) {
stringstream ss;
ss << i;
stringstream ss2;
ss2 << char_A;
ht.insert(make_pair(ss.str(), ss2.str()));
}

return ht;
}

string make_code(const string &s, string &bits, unordered_map<int, string> &pairs) {
unordered_map<string, string> ht = generate_char_ht();
string code;
int pair_count = 0;

for (int i = 0; i < s.size(); i++) {
auto it = pairs.find(i);

if (it != pairs.end()) {
string bit_str = bits.substr(bits.size() - pair_count - 1, 1);

if (bit_str == "1") {
auto it2 = ht.find(it->second);
code += it2->second;
i++;
}
else {
string tmp;
tmp.push_back(s[i]);
auto it2 = ht.find(tmp);
code += it2->second;
}

pair_count++;
}
else {
string tmp;
tmp.push_back(s[i]);
auto it2 = ht.find(tmp);
code += it2->second;
}
}

return code;
}

set<string> generate_code(const string &s1) {
set<string> vec;
unordered_map<int,string> pairs;
int intersec = 0;

for (int i = 10; i <= alphabet_size; i++) {
string tmp;
string s = s1;
stringstream ss;
ss << i;
ss >> tmp;
int j;

while (((j = s.find(tmp))) != -1) {
if (pairs.find(j - 1) == pairs.end() && pairs.find(j + 1) == pairs.end()) {
intersec++;
}

pairs.insert(make_pair(j, s.substr(j, 2)));
s.erase(s.begin(), s.begin() + j + 2);
}
}

for (int i = 0; i < pow(2, pairs.size()); i++) {
bitset<20> n(i);
string bitset_str = n.to_string().substr(n.size() - pairs.size(), pairs.size());

vec.insert(make_code(s1, bitset_str, pairs));
}

return vec;
}

int main() {
set<string> code = generate_code("1123");
// print code...

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The following is my solution in Objective-C

``````- (NSString *)getCharStringFromCode:(NSInteger)code {
NSString *rtString = @"";
if (code>=1 && code<=26) {
rtString = [NSString stringWithFormat:@"%c", 'a'+ code - 1];
}
return rtString;
}

- (void)stringFromAlphabetCodes:(NSArray *)codes currentString:(NSString *)currentString currentIndex:(NSUInteger)index returnArray:(NSMutableArray *)rtArray{
if ([codes count] > index) {
NSInteger singleCode = [codes[index] integerValue];
if (index + 1 < [codes count]) {
NSInteger afterCode = [codes[index+1]integerValue];
NSInteger twoCodes = singleCode*10+afterCode;
if (afterCode == 0) {
NSString *currStr = [currentString stringByAppendingString:[self getCharStringFromCode:twoCodes]];
[self stringFromAlphabetCodes:codes currentString:currStr currentIndex:index+2 returnArray:rtArray];
}
else if (twoCodes > 0 && twoCodes < 27) {
NSString *currStr = [currentString stringByAppendingString:[self getCharStringFromCode:singleCode]];
[self stringFromAlphabetCodes:codes currentString:currStr currentIndex:index+1 returnArray:rtArray];
currStr = [currentString stringByAppendingString:[self getCharStringFromCode:twoCodes]];
[self stringFromAlphabetCodes:codes currentString:currStr currentIndex:index+2 returnArray:rtArray];
}
else if (twoCodes > 26) {
NSString *currStr = [currentString stringByAppendingString:[self getCharStringFromCode:singleCode]];
[self stringFromAlphabetCodes:codes currentString:currStr currentIndex:index+1 returnArray:rtArray];
}
}
else {
NSString *currStr = [currentString stringByAppendingString:[self getCharStringFromCode:singleCode]];
[self stringFromAlphabetCodes:codes currentString:currStr currentIndex:index+1 returnArray:rtArray];
}
}
else {
}
}``````

Test case:

``````NSArray *codes = @[@"1",@"0",@"2",@"7",@"1",@"2",@"3"];
NSMutableArray *mArray = [NSMutableArray array];
[self stringFromAlphabetCodes:codes currentString:@"" currentIndex:0 returnArray:mArray];
NSLog(@"%@", mArray);
(
jbgabc,
jbgaw,
jbglc
)``````

Comment hidden because of low score. Click to expand.
0

I modified my code, to fix error when "0" is in the codes

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public Set<String> decode(String prefix , String code){
Set<String> set = new HashSet<String>();
if(code.length() == 0){
return set;
}
if(code.charAt(0)=='0'){
return set;
}
set.addAll(decode(prefix+(char)(code.charAt(0) - '1' + 'a'), code.substring(1)));

if(code.length() <2) return set;
int tem = (code.charAt(0)-'0') *10 + code.charAt(1) - '0';
if(tem > 26) return set;
set.addAll(decode(prefix + (char)(tem + 'a' -1) , code.substring(2));
return set;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The correct code in C++. Enjoy!

``````#include <bits/stdc++.h>
using namespace std;

void combinations(string prefix, string code)
{
if(code.length()==0)
{
cout<<prefix<<endl;
return;
}
if (code[0]=='0')
{
cout<<prefix<<endl;
return;
}
char temp=(code[0]-'1'+'a');
combinations(prefix+temp,code.substr(1));
if(code.length()>=2 && code[0]=='1')
{
temp=(10+code[1]-'1'+'a');
combinations(prefix+temp,code.substr(2));
}
if(code.length()>=2 && code[0]=='2'&&code[1]<='6')
{
temp=20+code[1]-'1'+'a';
combinations(prefix+temp,code.substr(2));
}
}

int main()
{
string s ="1123";
combinations("",s);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

PHP version:

``````function numberToPossibleStrings(\$num, \$numToCharMap) {
// convert number to string, extract digits
\$numLen = strlen("\$num");

// no possible matches, return empty
if (\$numLen == 0 || \$num == 0) {
return array();
}

// init an array with element 0 pre filled
\$combinations = array('');

// init our recursive algo
processDigit(\$num, \$numLen, 0, \$combinations, 0, \$numToCharMap);

return \$combinations;
}

function processDigit(\$num, \$numLen, \$numAt, &\$combinations, \$combinationsAt, \$numToCharMap) {
// verify we are within index
if (\$numAt >= \$numLen) {
return;
}

\$singleNum = substr("\$num", \$numAt, 1);

// if current digit is 0, move ahead one space
if (\$singleNum == 0) {
return processDigit(\$num, \$numLen, \$numAt + 1, \$combinations, \$combinationsAt, \$numToCharMap);
}

// handle double case first, as it creates a new array item
if (\$numAt + 1 < \$numLen) {
\$doubleNum = (int)substr("\$num", \$numAt, 2);
if (\$doubleNum < 27) {
// doubles create a new entry, and increment the combinations offset
\$combinations[] = \$combinations[\$combinationsAt] . \$numToCharMap[\$doubleNum];
processDigit(\$num, \$numLen, \$numAt + 2, \$combinations, count(\$combinations) - 1, \$numToCharMap);
}
}

// handle single case
\$combinations[\$combinationsAt] = \$combinations[\$combinationsAt] . \$numToCharMap[\$singleNum];
processDigit(\$num, \$numLen, \$numAt + 1, \$combinations, \$combinationsAt, \$numToCharMap);
}

// setup number to char map
\$numToCharMap = array();

for (\$j = 1; \$j < 27; \$j++) {
\$numToCharMap[\$j] = chr(\$j + 96);
}

print_r(numberToPossibleStrings(1123, \$numToCharMap));
print_r(numberToPossibleStrings(1010, \$numToCharMap));
print_r(numberToPossibleStrings(1000, \$numToCharMap));
print_r(numberToPossibleStrings(237811487, \$numToCharMap));``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a recursive solution in Objective-C, composed of two classes:

1. `NSString (CCPCharacterCode)` is a category on `NSString` that converts a string between `@"1"` and `@"26"` to a string containing an letter between `@"a"` and `@"z"`.
2. `CCPCodeParser` parses a code and stores the results in a `results` property.

I believe the complexity is `O(n^2)`, but I'm not 100% sure.

``````// NSString+CCPCharacterCode.h

#import <Foundation/Foundation.h>

@interface NSString (CCPCharacterCode)

/**
Converts a string representing a single- or double-digit integer
to a string representing a character matching that integer,
where a = 1, b = 2, and so on until z = 26.

Raises an exception if code represents an integer outside the
range of [1, 26].

Complexity is O(1).
*/
+ (NSString *)stringWithCharacterCode:(NSString *)code;

@end``````

``````// NSString+CCPCharacterCode.m

#import "NSString+CCPCharacterCode.h"

@implementation NSString (CCPCharacterCode)

#pragma mark - Public Interface

+ (NSString *)stringWithCharacterCode:(NSString *)code {
int value = [code intValue];
NSParameterAssert(value >= 1 && value <= 26);

return [NSString stringWithFormat:@"%c", 'a' - 1 + value];
}

@end``````

``````// CCPCodeParser.h

#import <Foundation/Foundation.h>

@interface CCPCodeParser : NSObject

/**
The results of one or more calls to -parse:.
If -parse: has not yet been called, or if -parse: has only been
called with an empty strings, this is an empty set.
*/

/**
Parses a code composed of digits within the range [1, 26]
and stores the results in -results.

Raises an exception if code is nil, or if it contains digits
outside of the range [1, 26].

Complexity is O(n^2).
*/
- (void)parse:(NSString *)code;

@end``````

``````// CCPCodeParser.m

#import "CCPCodeParser.h"
#import "NSString+CCPCharacterCode.h"

@interface CCPCodeParser ()
@property (nonatomic, strong) NSMutableSet *parsed;
@end

@implementation CCPCodeParser

#pragma mark - Object Lifecycle

- (instancetype)init {
self = [super init];
if (self) {
_parsed = [NSMutableSet set];
}
return self;
}

#pragma mark - Public Interface

- (NSSet *)results {
return [self.parsed copy];
}

- (void)parse:(NSString *)code {
NSParameterAssert(code != nil);
[self parse:code prefix:@""];
}

#pragma mark - Internal Methods

- (void)parse:(NSString *)code prefix:(NSString *)prefix {
if ([code length] >= 2) {
[self parseTwoDigitsIfValidCode:code prefix:prefix];
[self parseOneDigit:code prefix:prefix];
} else if ([code length] == 1) {
[self parseOneDigit:code prefix:prefix];
} else if ([prefix length] > 0) {
}
}

- (void)parseOneDigit:(NSString *)code prefix:(NSString *)prefix {
NSString *digit = [code substringWithRange:NSMakeRange(0, 1)];
prefix = [NSString stringWithFormat:@"%@%@", prefix, [NSString stringWithCharacterCode:digit]];
[self parse:[code substringFromIndex:1] prefix:prefix];
}

- (void)parseTwoDigitsIfValidCode:(NSString *)code prefix:(NSString *)prefix {
NSString *digits = [code substringWithRange:NSMakeRange(0, 2)];
if ([digits intValue] <= 26) {
prefix = [NSString stringWithFormat:@"%@%@", prefix, [NSString stringWithCharacterCode:digits]];
[self parse:[code substringFromIndex:2] prefix:prefix];
}
}

@end``````

Comment hidden because of low score. Click to expand.
0

I forgot to include the test file:

``````// CCPCodeParserSpec.m

#import <Kiwi/Kiwi.h>
#import "CCPCodeParser.h"

SPEC_BEGIN(CCPCodeParserSpec)

describe(@"CCPCodeParser", ^{
__block CCPCodeParser *parser = nil;
__block NSString *code = nil;
beforeEach(^{
parser = [CCPCodeParser new];
});

describe(@"-parse:", ^{
context(@"when the code is nil", ^{
it(@"raises", ^{
[[theBlock(^{ [parser parse:code]; }) should] raise];
});
});

context(@"when the code is empty", ^{
beforeEach(^{ code = @""; });
[parser parse:code];
[[parser.results should] beEmpty];
});
});

context(@"when the code is not empty", ^{
context(@"but it contains digits outside of range [1, 26]", ^{
beforeEach(^{ code = @"1020"; });
it(@"raises", ^{
[[theBlock(^{ [parser parse:code]; }) should] raise];
});
});

context(@"and it only contains digits within range [1, 26]", ^{
beforeEach(^{ code = @"1123"; });
it(@"parses the code", ^{
[parser parse:code];

[[theValue([parser.results count]) should] equal:@5];
[[parser.results should] contain:@"aabc"];
[[parser.results should] contain:@"kbc"];
[[parser.results should] contain:@"alc"];
[[parser.results should] contain:@"aaw"];
[[parser.results should] contain:@"kw"];
});
});
});
});
});

SPEC_END``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

There's two steps (assuming you only have digits 1-9)

1. Create a partition of the numbers: for example, 6121371 is partitioned into (6,1213,7,1). This is straightforward by walking through two digits at a time, and splitting in the middle if the number is greater than 26.

In Python this takes two lines:

``idx = [ ii+1 for ii in range(len(s)-1) if int(s[ii:ii+2])>26 ]``

``perms = [ s[L:R] for L, R in zip(idx[:-1], idx[1:]) ]``

2. At this point you only have to get the possible combinations on each partition; this can be done (for example) with DP or just walking through it in O(K^2) time, where K is the size of the partition. If max(K) << N (length of the full string), e.g. for randomly-chosen digits, the walkthrough in Step 1 of O(N) dominates. Worst-case scenario the digits aren't randomly chosen (e.g. there's lots of 1's and 2's) and you're dealing with O(N^2)

Comment hidden because of low score. Click to expand.
0
of 0 vote

The simplest solution

``````public static void generate(String input, int start, String resutl) {
if (start >= input.length()) {
System.out.println(resutl);
return;
}
int firstNumber = Integer.parseInt(input.substring(start, start + 1));
String newResult = resutl + (char) (firstNumber + 96);//96 is the asci code
generate(input, start + 1, newResult);
if (start <= input.length() - 2) {
int secondNumber = Integer.parseInt(input.substring(start, start + 2));
newResult = resutl + (char) (secondNumber + 96);
generate(input, start + 2, newResult);//96 is the asci code

}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include<stdio.h>
#include<string.h>
int main()
{
int temp,i,j,sum=0;
char s[10],str[]={'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'};
scanf("%s",s);
for(i=0;i<strlen(s);i++)
{
for(j=0;j<strlen(str);j++)
{
temp=0;
if(s[i]==str[j])
{
temp=j;
temp=temp+1;
sum+=temp;
break;
}
}
}
printf("%d",sum);

return 0;
}``````

Comment hidden because of low score. Click to expand.
0

any doubt put msg in my inbox aravindan401@gmail.com

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void printCodes(string in, string soFar)
{
int n = 0;

if(in.size() <= 0) {
cout<<soFar<<endl;
return;
}

n = atoi(in.substr(0, 1).c_str());
printCodes(in.substr(1, in.size() - 1), soFar + alphabet[n]);

if(in.size() > 1) {
n = atoi(in.substr(0, 2).c_str());
printCodes(in.substr(2, in.size() - 2), soFar + alphabet[n]);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````void printCodes(string in, string soFar)
{
int n = 0;

if(in.size() <= 0) {
cout<<soFar<<endl;
return;
}

n = atoi(in.substr(0, 1).c_str());
printCodes(in.substr(1, in.size() - 1), soFar + alphabet[n]);

if(in.size() > 1) {
n = atoi(in.substr(0, 2).c_str());
printCodes(in.substr(2, in.size() - 2), soFar + alphabet[n]);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python, O(2^(n-1)) as it is. Non-recursive, iterative, No dynamic programming.

The O(2^(n-1)) comes from generating all permutations of binary states from getBinaryStates().

Approach: combinatorics and permutations reasoning.

Edit: O(n) can be achieved by simply combining removeOverlap() into getBinaryState(). (i.e. so that if the left most bit of the previous groups of states start with 1, such as {(1), (10, 11), (100, 101,...111), (1000, 1001, 1010, ... 1111)}, then just makes sure that we skip over prepending the new left most bit with 1, since '11' is not allowed.)

``````def findAllCodes(s):
length = len(s)
nPairs = length - 1

possibleStates = getBinaryStates(nPairs)
discreteStates = removeOverlap(possibleStates)
validStates = getValidStates(s, discreteStates)

print 'Number of strings generated:', len(validStates)

for state in validStates:
codeArr = convertToCode(state, s)
print "".join(convertToAlpha(codeArr)), '->', codeArr

def convertToAlpha(codeArr):
d = dict()
i = 1
while i < 27:
d[i] = chr(ord('a')+i-1)
i += 1

output = []
for code in codeArr:
output += d[int(code)]

return output

def convertToCode(state, s):
output = []

# loop over binary places
j = 0
i = 0
while j < len(state):

# turn all binary 0 to code (simply take the single digit number)
while state[j] != '1':
output += [ s[i] ]
j += 1
i += 1

if j > len(state)-1:
break

# arrived at first binary 1, take the next 2 digits, combine as single number
else: # state[j] == '1'
output += [ s[i] + s[i+1] ]
i += 2 # shift 2 indice because we've used s[i] + s[i+1]
j += 2

# turn the remaining binary 0 to code
while i <= len(s)-1:
output += [ s[i] ]
i += 1
return output

def getBinaryStates(n):
possibleStates = []

for i in range(2**n):
binary = bin(i)[2:]
if len(binary) != n:
binary = '0'*(n - len(binary))+binary

possibleStates += [binary]
return possibleStates

def removeOverlap(possibleStates):
discreteStates = []
for state in possibleStates:

# Remove pairs whose index overlaps
if "11" not in state:
discreteStates += [state]
return discreteStates

def getValidStates(s, discreteStates):
validStates = []
for state in discreteStates:

keep_flag = 1

for index in range(len(state)):
chrNum = int(s[index]+s[index+1])
# Remove pairs whose letter corresponds values bigger than z=26
if (state[index]=='1') and chrNum > 26:
keep_flag = 0

if keep_flag == 1:
validStates += [state]
return validStates

if __name__ == '__main__':
s = "1123"
s2 = '1422616325'
findAllCodes(s)
findAllCodes(s2)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Test{
public int ASCII_CODING_DIFF = 67;
private Map<String, Character> codes = new HashMap<String, Character>();
public Test(){
for(char c = 'a'; c<='z'; c++){
int code = c - ASCII_CODING_DIFF + 1;//67
codes.put(code, c);
}
}

public List<StringBuilder> getCombos(String str, int start){
List<StringBuilder> combos = new ArrayList<StringBuidler>();
if(start >= str.length)
combos;
int end = start + 1;
String firstChar = str.subString(start, end+1);//check the javadoc for subString() for what start and end should be. Could be off by 1 here.
while(codes.contains(firstChar)){
Character code = codes.get(firstChar);
List<StringBuilder> subCombos = getCombos(str, end);
for(StringBuilder subCombo : subCombos){
}
}
return combos;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution on the problem :
ArrayList<Character> result = new ArrayList<Character>();

public void decode(String word, int k,int n) {

if (k == n) {
for(int i = 0;i<result.size();i++){
System.out.print(result.get(i));
}
System.out.println();
}
for(int i = 1; i <= n-k; i++) {
String prefix = word.substring(k,k+i);
int iVal = Integer.parseInt(prefix);
if (iVal < 27) {
char codedChar = (char)('a'+iVal-1);
decode(word, k+prefix.length(),n);
result.remove(result.size()-1);
}
}
}
decode("1123",0,"1123".length());

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution on the problem :

``````static ArrayList<Character> result = new  ArrayList<Character>();

public static void decode(String word, int k,int n) {

if (k == n) {
for(int i = 0;i<result.size();i++){
System.out.print(result.get(i));
}
System.out.println();
}
for(int i = 1; i <= n-k; i++) {
String prefix = word.substring(k,k+i);
int iVal = Integer.parseInt(prefix);
if (iVal < 27) {
char codedChar = (char)('a'+iVal-1);
decode(word, k+prefix.length(),n);
result.remove(result.size()-1);
}
}
}
decode("1123",0,"1123".length());``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void f(char* pre, int pl, char const *a, int al) {
static int count = 0;
if (al == 0) {
count++;
printf("%s %d\n", pre, count);
return;
}
if (al >= 1) {
char p = a[0] - '0' - 1 + 'a';
pre[pl] = p; pre[pl+1] = '\0';
f(pre, pl+1, a+1, al-1);
pre[pl] = '\0';
}
if (al >= 2) {
char p = (a[0] - '0')*10 + (a[1] - '0') - 1 + 'a';
pre[pl] = p; pre[pl+1] = '\0';
f(pre, pl+1, a+2, al-2);
pre[pl] = '\0';
}
return;
}

void func(char const *a) {
int al = strlen(a);
char *pre = (char*)malloc(strlen(a) + 1);
pre[0] = '\0';
f(pre, 0, a, al);
free(pre);
}

int main(void) {
char const *a = "1123";
func(a);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void f(char* pre, int pl, char const *a, int al) {
static int count = 0;
if (al == 0) {
count++;
printf("%s %d\n", pre, count);
return;
}
if (al >= 1) {
char p = a[0] - '0' - 1 + 'a';
pre[pl] = p; pre[pl+1] = '\0';
f(pre, pl+1, a+1, al-1);
pre[pl] = '\0';
}
if (al >= 2) {
char p = (a[0] - '0')*10 + (a[1] - '0') - 1 + 'a';
pre[pl] = p; pre[pl+1] = '\0';
f(pre, pl+1, a+2, al-2);
pre[pl] = '\0';
}
return;
}

void func(char const *a) {
int al = strlen(a);
char *pre = (char*)malloc(strlen(a) + 1);
pre[0] = '\0';
f(pre, 0, a, al);
free(pre);
}

int main(void) {
char const *a = "1123";
func(a);
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Got this question over a phone interview and locked up trying to solve it in linear time.. afterwards came up with this for a recursive python solution.

``````user_input = '111110'

L = {str(i+1):x for i, x in enumerate(list('abcdefghijklmnopqrstuvwxyz'))}

combinations = []
def next(current, remainder):
if not remainder:
combinations.append(current)
return

# take single
next_single = L.get(remainder[0], None)
if not next_single:
return
next(current + next_single, remainder[1:])

# take double
if len(remainder) >= 2:
next_double = L.get(remainder[0] + remainder[1], None)
if not next_double:
return
next(current + next_double, remainder[2:])

next('', list(user_input))

print combinations``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <string>
#include <iostream>
#include <vector>
using namespace std;

void strcode(const string& str, unsigned p, const vector<string>& prefixes, const string& code)
{
if (p == str.size())
{
cout << code << endl;
return;
}

for(int i = 0; i < 26; ++i)
{
string prefix = prefixes[i];
if (prefix == str.substr(p, prefix.size()))
strcode(str, p + prefix.size(), prefixes, code + char('a'+i));
}
}

int main(int argc, char *argv[])
{
string input = "1123";
vector<string> prefixes(26);
for(int i = 0; i < 26; ++i)
prefixes[i] = to_string(i+1);
strcode(input, 0, prefixes, "");
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Do you have to give the optimal DP solution to pass if you are given this question? I only got the recursive solution completely :( I had the right approach with the DP but made some errors in my code and couldn't finish the DP in time :(

Comment hidden because of low score. Click to expand.
0
of 0 vote

In Swift based on Antonio081014 answer.

Time complexity is O(fib(N)) (Confirmed with Xcode Playground). Anyone could explain for me why? Thanks!

``````func map(characters: [Character]) -> String.CharacterView? {
let table: [String: String] = [
"1" : "a",
"2" : "b",
"3" : "c",
"4" : "d",
"5" : "e",
"6" : "f",
"7" : "g",
"8" : "h",
"9" : "i",
"10" : "j",
"11" : "k",
"12" : "l",
"13" : "m",
"14" : "n",
"15" : "o",
"16" : "p",
"17" : "q",
"18" : "r",
"19" : "s",
"20" : "t",
"21" : "u",
"22" : "v",
"23" : "w",
"24" : "x",
"25" : "y",
"26" : "z",
]
return table[String(characters)]?.characters
}

func decode(prefix: String.CharacterView, characters: String.CharacterView) -> Set<String> {
var set = Set<String>()

if characters.isEmpty {
set.insert(String(prefix))
return set
}

let startIndex = characters.startIndex
let character = characters[startIndex]

if let mappedCharacter = map([character]) {
set.unionInPlace(decode(prefix + mappedCharacter, characters: characters.suffixFrom(startIndex.successor())))
}
if characters.count >= 2 {
let nextIndex = startIndex.successor()
let nextCharacter = characters[nextIndex]

if let mappedCharacter = map([character, nextCharacter]) {
set.unionInPlace(decode(prefix + mappedCharacter, characters: characters.suffixFrom(nextIndex.successor())))
}
}
return set
}

print(decode("".characters, characters: characters))``````

Comment hidden because of low score. Click to expand.
0

Sorry for the double posting. I registered an account and post the same answer.

Comment hidden because of low score. Click to expand.
0
of 0 vote

In Swift, based on Antonio081014 answer.

The time complexity based on benchmark is fib(N) but I couldn't fully explain why? Anyone have any insight on this?

``````let text = "122222222226"
let characters = text.characters

func map(characters: [Character]) -> String.CharacterView? {
let table: [String: String] = [
"1" : "a",
"2" : "b",
"3" : "c",
"4" : "d",
"5" : "e",
"6" : "f",
"7" : "g",
"8" : "h",
"9" : "i",
"10" : "j",
"11" : "k",
"12" : "l",
"13" : "m",
"14" : "n",
"15" : "o",
"16" : "p",
"17" : "q",
"18" : "r",
"19" : "s",
"20" : "t",
"21" : "u",
"22" : "v",
"23" : "w",
"24" : "x",
"25" : "y",
"26" : "z",
]
return table[String(characters)]?.characters
}

func decode(prefix: String.CharacterView, characters: String.CharacterView) -> Set<String> {
var set = Set<String>()

if characters.isEmpty {
set.insert(String(prefix))
return set
}

let startIndex = characters.startIndex
let character = characters[startIndex]

if let mappedCharacter = map([character]) {
set.unionInPlace(decode(prefix + mappedCharacter, characters: characters.suffixFrom(startIndex.successor())))
}
if characters.count >= 2 {
let nextIndex = startIndex.successor()
let nextCharacter = characters[nextIndex]

if let mappedCharacter = map([character, nextCharacter]) {
set.unionInPlace(decode(prefix + mappedCharacter, characters: characters.suffixFrom(nextIndex.successor())))
}
}
return set
}

print(decode("".characters, characters: characters))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class ques{
public static String[] code(String input,String[] charArray) {
if(input.length()==1)
{
String[] str = new String[1];
str[0] = charArray[input.charAt(0)-48];
return str;
}

if(input.length()==2)
{
if(input.charAt(0)-48<=2)
{
if(input.charAt(1)-48<=6)
{
String[] str = new String[2];
str[0] = charArray[input.charAt(0)-48] + charArray[input.charAt(1)-48];
int x = ((int)(input.charAt(0))-48)*10 + (int)(input.charAt(1)-48);
str[1] = charArray[x];
return str;
}else
{
String[] str = new String[2];
str[0] = charArray[input.charAt(0)-48];
str[1] = charArray[input.charAt(1)-48];
return str;
}
}else
{
String[] str = new String[1];
str[0] = charArray[input.charAt(0)-48];
str[1] = charArray[input.charAt(1)-48];
return str;

}
}

String[] n1 = code(input.substring(1), charArray);
String[] n2 = code(input.substring(2), charArray);
String[] str = new String[n1.length + n2.length];
int i = 0;
while(i<n1.length)
{
n1[i] = charArray[input.charAt(0)-48] + n1[i];
str[i] = n1[i];
i++;
}
int k = i;
i = 0;
int x = ((int)(input.charAt(0))-48)*10 + (int)(input.charAt(1)-48);

if(input.charAt(0)-48<=2)
{
if(input.charAt(1)-48<=6)
{
while(i<n2.length)
{
n2[i] =charArray[x] + n2[i];
str[k] = n2[i];
k++;
i++;
}
}
}
return str;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
String[] charArray = new String[27];
int i = 1;
char ch = 'a';
while(i<charArray.length)
{
charArray[i] = String.valueOf(ch);
ch++;
i++;
}
String[] str1;
str1 = code("1123", charArray);
int k = 0;
while(k<str1.length)
{
System.out.println(str1[k]);
k++;
}
}
}``````

kindly let me know if you find any bugs.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private static void getValidLists(Map<Integer, String> charsMap, String s, List<List<String>> allPerms,
List<String> currentList) {
if (s == null) {
return;
}
if (s.length() == 0) {
return;
}
if (s.length() == 1) {
return;
}

List<String> copy = new ArrayList<>(currentList);
getValidLists(charsMap, s.substring(1), allPerms, copy);

String subString = s.substring(0, 2);
if (Integer.parseInt(subString) <= 26) {
getValidLists(charsMap, s.substring(2), allPerms, currentList);
}
}

private static String getEncodedString(Map<Integer, String> charsMap, String rawString) {
return charsMap.get(Integer.parseInt(rawString));
}

public static void main(String[] args) {
Map<Integer, String> charsMap = new HashMap<>();
for (int i = 0; i < 26; i++) {
charsMap.put(i + 1, String.valueOf((char) ('a' + i)));
}
List<List<String>> allPerms = new ArrayList<>();
getValidLists(charsMap, "1123", allPerms, new ArrayList<>());
System.out.println(allPerms);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The idea is that, looking at the number from the right-most digits, you break out one or two characters, then recursively post-fix these broken out characters to all permutations of the remainder of the string.

Example:

1123

Step 1 (post-fix: ''):
Look at right-most characters: 23.
This is less than 26, so we can have 11+w (Step 2a) or 112+c (Step 2b).

Step 2a (post-fix: 'w'):
Look at right-most characters: 11
This is less than 26, so we can have +kw or 1+aw

Step 2b (post-fix: 'c'):
Right-most characters: 12
Less than 26, so we can have 1+lc or 11+bc

... and so on

Here is the code in Objective-C.

``````#include <Foundation/Foundation.h>

char charForNum(int num) {
if (num == 0) {
return '_';
}

if (num > 26) {
return '?';
}

return 'a' + num - 1;
}

NSArray* numberPermutations(int num, NSString *postFix) {
if (num == 0) {
return [NSArray arrayWithObject:postFix];
}

if (num < 10) {
return [NSArray arrayWithObject:[NSString stringWithFormat:@"%c%@",
charForNum(num), postFix]];
}

int lastTwoDigits = num % 100;
int right = lastTwoDigits % 10;
NSArray* takeOne = numberPermutations(num / 10, [NSString stringWithFormat:@"%c%@",
charForNum(right), postFix]);
if (lastTwoDigits > 26 || lastTwoDigits < 10) {
return takeOne;
} else {
NSArray* takeTwo = numberPermutations(num / 100, [NSString stringWithFormat:@"%c%@",
charForNum(lastTwoDigits), postFix]);
}
}

int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray* perms = numberPermutations(112334054, @"");
for (NSString* perm in perms) {
NSLog(@"%@", perm);
}
}
return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void main(String[] args) {

HashMap<String, String> hm = new HashMap<String, String>();
hm.put("1", "a");
hm.put("2", "b");
hm.put("3", "c");
hm.put("4", "d");
hm.put("5", "e");
hm.put("6", "f");
hm.put("7", "g");
hm.put("8", "h");
hm.put("9", "ai");
hm.put("10", "j");
hm.put("11", "k");
hm.put("12", "l");
hm.put("13", "m");
hm.put("14", "n");
hm.put("15", "o");
hm.put("16", "p");
hm.put("17", "q");
hm.put("18", "r");
hm.put("19", "s");
hm.put("20", "t");
hm.put("21", "u");
hm.put("22", "v");
hm.put("23", "w");
hm.put("24", "x");
hm.put("25", "y");
hm.put("26", "z");
List<String> str = decode("1123", hm);
for (int i = 0; i < str.size(); i++) {
System.out.println(str.get(i));
}
}

static List<String> decode(String str, HashMap<String, String> hm) {

List<String> strArr = new ArrayList<String>();
if (str.length() == 1) {

} else if (str.length() == 2) {

strArr.add(hm.get("" + str.charAt(0)) + hm.get("" + str.charAt(1)));

if (Integer.parseInt(str) <= 26) {
}

} else {
String firstChar = "" + str.charAt(0) + str.charAt(1);

List<String> lst = decode(str.substring(1), hm);

for (int i = 0; i < lst.size(); i++) {
}

String firstTwoChars = "" + str.charAt(0) + str.charAt(1);

lst = decode(str.substring(2), hm);

if (Integer.parseInt(firstTwoChars) <= 26) {
for (int i = 0; i < lst.size(); i++) {
}
}

}
return strArr;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````st = [chr(i) for i in range(ord('a'), ord('z') + 1)]
a = [1,1,2,3]

def rec(a,s,i):
if i>=len(a):
print s
return

rec(a,s+st[a[i]-1],i+1)
if i<len(a)-1:
num = int(str(a[i])+str(a[i+1]))
if num < 26:
rec(a,s+st[num-1],i+2)

stri =""
rec(a,stri,0)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````st = [chr(i) for i in range(ord('a'), ord('z') + 1)]
a = [1,1,2,3]

def rec(a,s,i):
if i>=len(a):
print s
return

rec(a,s+st[a[i]-1],i+1)
if i<len(a)-1:
num = int(str(a[i])+str(a[i+1]))
if num < 26:
rec(a,s+st[num-1],i+2)

stri =""
rec(a,stri,0)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*  ZoomBA : Recursive */
A = ['a':'z'].string
\$count = 0
def decode( string , result ){
if ( (len = #|string|) == 0 ) {
\$count += 1 ; println( result )
return
}
if ( (inx = int(string.0) ) == 0 ) return
// now the rest
decode ( string[1:-1] ,  result + A[inx - 1] )
if ( len > 1 ){
two = string[0:1] ; inx = int(two)
if ( inx < 27 ){
decode ( string[2:-1] ,  result + A[inx - 1] )
}
}
}
ip = '1123'
decode(ip,'')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*  ZoomBA : with Join */
A = ['a':'z'].string
def decode(string){
len = #|string|
join_args = fold( [ 0:len ] , list() ) -> {
inx = int ( string[\$.o] )
continue( inx == 0 )
options = list('')
options +=  A[inx-1]
if ( \$.o + 1 < len ){
inx = int( str(string[\$.o]) + string[\$.o + 1] )
if ( inx < 27 ){ options +=  A[inx-1] }
}
\$.p.add ( options ) ; \$.p
}
join( @ARGS = join_args ) :: {
w = str(\$.o,'')
str( w.value ,'' ) -> { \$.o - 96 } == string
} -> { str(\$.o,'') }
}
ip = '1123'
words = decode(ip)
println( words )``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

n = 0
def output(input, original, pre):
global n

if len(original) in(0,1):
#add last mapping to the string
if len(original) == 1:
pre += input.get(original[0:1])
n += 1
cm=[]
for detail in pre:
for x, y in input.items():
if y == detail:
cm.append(detail + "=" + x )
#list string wih mapping detail
print (" %5d %s ==> %s"%(n, pre, cm))
return

#if there are 2 digits mapping
if input.get(original[0:2]) != None :
new_chr = input.get(original[0:2])
output(input, original[2:], pre + new_chr)

#single digits mapping
new_chr = input.get(original[0:1])
output(input, original[1:], pre + new_chr)

if __name__ == '__main__':
import sys
sys.stdout = open('c:\\temp\\output.txt', 'wt')
starter = 0 #start mapping a -> 0 change to 1 if a ->1
input_mapping = {str(x):y for x in range(starter, starter+26) for y in chr(97 + x)}
print("input mapping %s" %input_mapping)
input = '234132598022231224433110010022'
print ("your input : %s:" %input)
output(input_mapping, input, '')

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````n = 0
def output(input, original, pre):
global n

if len(original) in(0,1):
#add last mapping to the string
if len(original) == 1:
pre += input.get(original[0:1])
n += 1
cm=[]
for detail in pre:
for x, y in input.items():
if y == detail:
cm.append(detail + "=" + x )
#list string wih mapping detail
print (" %5d %s  ==> %s"%(n, pre, cm))
return

#if there are 2 digits mapping
if input.get(original[0:2]) != None :
new_chr = input.get(original[0:2])
output(input, original[2:], pre + new_chr)

#single digits mapping
new_chr = input.get(original[0:1])
output(input, original[1:], pre + new_chr)

if __name__ == '__main__':
import sys
sys.stdout = open('c:\\temp\\output.txt', 'wt')
starter = 0  #start mapping a -> 0 change to 1 if a ->1
input_mapping = {str(x):y for x in range(starter, starter+26) for y in chr(97 + x)}
print("input mapping %s" %input_mapping)
input = '234132598022231224433110010022'
print ("your input : %s:" %input)
output(input_mapping, input, '')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````n = 0
def output(input, original, pre):
global n

if len(original) in(0,1):
#add last mapping to the string
if len(original) == 1:
pre += input.get(original[0:1])
n += 1
cm=[]
for detail in pre:
for x, y in input.items():
if y == detail:
cm.append(detail + "=" + x )
#list string wih mapping detail
print (" %5d %s  ==> %s"%(n, pre, cm))
return

#if there are 2 digits mapping
if input.get(original[0:2]) != None :
new_chr = input.get(original[0:2])
output(input, original[2:], pre + new_chr)

#single digits mapping
new_chr = input.get(original[0:1])
output(input, original[1:], pre + new_chr)

if __name__ == '__main__':
import sys
sys.stdout = open('output.txt', 'wt')
starter = 0  #start mapping a -> 0 change to 1 if a ->1
input_mapping = {str(x):y for x in range(starter, starter+26) for y in chr(97 + x)}
print("input mapping %s" %input_mapping)
input = '234132598022231224433110010022'
print ("your input : %s:" %input)
output(input_mapping, input, '')``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

C# Solution

``````public static int DecodeLength(String code)
{
if (code.Length == 0) return 1;
if (code[0] == '0') return 0;

int res = DecodeLength(code.Substring(1));
if (code.Length >= 2 && (code[0] == '1' || (code[0] == '2' && code[1] <= '6')))
res += DecodeLength(code.Substring(2));
return res;
}``````

And linear solution using DP

``````static Dictionary<string, int> _CodesDic = new Dictionary<string, int>();
public static int DecodeLengthDP(String code)
{
if (code.Length == 0) return 1;
if (code[0] == '0') return 0;
if (_CodesDic.ContainsKey(code)) return _CodesDic[code];

int res = DecodeLengthDP(code.Substring(1));
if (code.Length >= 2 && (code[0] == '1' || (code[0] == '2' && code[1] <= '6')))
res += DecodeLengthDP(code.Substring(2));
if (!_CodesDic.ContainsKey(code))
return res;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#!/usr/bin/python
from binarytree import Node, setup, tree, pprint

class MyTree(object):
def __init__(self, initial):
self.root = Node(initial)

def __repr__(self):
pprint(self.root)
return ''

#
# Decode 's' into a tree starting at root.
# The format of the output tree is binary with values less
# than the current node on the left and values greater than on
# the right.
#
def decode_str(s, root):
if not len(s):
return

# have at least 2 chars left in string
if len(s) > 1:
# create a new node with the next 2 chars
root.right = Node(s[:2])
# decode the rest of the string...
decode_str(s[2:], root.right)

# have at least 1 char left in string
if len(s) > 0:
# create a new node with the next 2 chars
root.left = Node(s[:1])
# decode the reset of the string...
decode_str(s[1:], root.left)

# Fills 'paths' will all unique paths through the tree
# via BFS.
def tree_paths(t, paths, path = None):
if not t:
return

if not path:
path = []

path.append(t.value)

if not t.left and not t.right:
paths.append(path)
else:
tree_paths(t.left, paths, path[:])
tree_paths(t.right, paths, path[:])

# Creates a mapping via a=1, b=2, c=3... z=26
def create_alphabet_map():
return {str(k+1):chr(v + 97) for k,v in enumerate(range(26))}

######
amap = create_alphabet_map()

t = MyTree("1123")
decode_str(t.root.value, t.root)
print t

# Do the left and right instead of root to avoid the input
# string as part of the paths
paths = []
tree_paths(t.root.left, paths)
tree_paths(t.root.right, paths)

print 'Total combos (tree paths):', len(paths)

for p in paths:
for c in p:
print amap[c],
print

#### output:
#
#
#	           _____1123____
#	          /             \
#	      ___1__             11
#	     /      \           /  \
#	    1        12        2    23
#	   / \      /         /
#	  2   23   3         3
#	 /
#	3
#
#
#	Total combos (tree paths): 5
#	a a b c
#	a a w
#	a l c
#	k b c
#	k w``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby:

``````alphabet = ("a".."z").to_a.inject({}) do |t, l|
t.merge((t.size + 1).to_s => l)
end

def find_codes(str, alphabet)
return [""] if str.empty?
p = []
str.size.times do |i|
b = str[0..i]
e = str[i + 1..-1]
if(alphabet[b])
p += find_codes(e, alphabet).map do |sub|
alphabet[b] + sub
end
end
end
p
end

p find_codes("1123", alphabet)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby:

``````alphabet = ("a".."z").to_a.inject({}) do |t, l|
t.merge((t.size + 1).to_s => l)
end

def find_codes(str, alphabet)
return [""] if str.empty?
p = []
str.size.times do |i|
b = str[0..i]
e = str[i + 1..-1]
if(alphabet[b])
p += find_codes(e, alphabet).map do |sub|
alphabet[b] + sub
end
end
end
p
end

p find_codes("1123", alphabet)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Ruby:

``````def repeats?(str)
list = {}
str.chars.each do |c|
list.values.each do |v|
if(v[:repeated] && v[c])
return true
end
v[c] = true
end
if(list[c])
list[c][:repeated] = true
else
list[c] = {}
end
end
return false
end

p repeats?("abab")
p repeats?("abba")
p repeats?("acbdaghfb")
p repeats?("abcdacb")``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

what's the significance of prefix in the argument list here? can the same code be done without the prefix String in the argument?

P.s. I am new to Data structures and learning recursions right now.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````-- partition the string into pairs and singles.
-- n = 1 : 1
-- n = 2 : 2
-- n = 3 : 3
-- n = 4 : C(3) + C(2)
-- n = 5 : C(4) + C(3)
-- C(n) = C(n-1) + C(n-2)
-- "solving" the recurrence relation gives O(n^2)
--
codes :: [Int] -> [[Char]]
codes =
let
charOf x
| x >= 1 && x <= 26 =
['a'..'z'] List.!! (x-1)
| otherwise =
Prelude.error ("invalid input: " <> show x)
choice xs =
case xs of
[] ->
[[]]
[x] ->
[[charOf x]]
x : y : zs ->
fmap (charOf x:) (choice (y:zs)) <>
fmap ((charOf (10*x+y)):) (choice zs)
in
choice``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Below is the working code using recursion, hope it helps :)

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
*
* @author Nalin.Sharma
*
*/

/*
* a = 1
* b = 2
* .
* .
* .
* input
* 112
* output
* aab
* kb(11 for k)
* al(12 for l)
*
*/

public static void main(String[] args) {

String s = "112";
char a [] = s.toCharArray();
Map<Integer,Character> map = new HashMap<>();
fill(map);
List<List<Integer>> all = new ArrayList<>();
List<Integer> l = prepareList(a);
rec(l, all);
print(all,map);
System.out.println();
}

private static void print(List<List<Integer>> all, Map<Integer, Character> map) {
for(List<Integer> l : all){
String out = "";
for (int i = 0; i < l.size(); i++) {
out += map.get(l.get(i));
}
System.out.println(out);
}
}

private static void rec(List<Integer> l, List<List<Integer>> all) {
for (int i = 0; i < l.size(); i++) {
if(i+1 < l.size() && l.get(i) < 9 && l.get(i+1) < 9){
int n = l.get(i) * 10 + l.get(i+1);
if(n<26){
List<Integer> lnew = new ArrayList<>(l);
lnew.remove(i+1);
lnew.set(i, n);
rec(lnew, all);
}
}
}
}

private static List<Integer> prepareList(char[] a) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < a.length; i++) {
}
return list;
}

private static void fill(Map<Integer, Character> map) {
char c;
for(int i =0 ; i < 26; i++){
c = (char) ('a' + i);
map.put(i+1 , c);
}
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my recursive solution hope it helps :)

``````import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
*
* @author Nalin.Sharma
*
*/

/*
* a = 1
* b = 2
* .
* .
* .
* input
* 112
* output
* aab
* kb(11 for k)
* al(12 for l)
*
*/

public static void main(String[] args) {

String s = "112";
char a []  = s.toCharArray();
Map<Integer,Character> map = new HashMap<>();
fill(map);
List<List<Integer>> all = new ArrayList<>();
List<Integer> l = prepareList(a);
rec(l, all);
print(all,map);
System.out.println();
}

private static void print(List<List<Integer>> all, Map<Integer, Character> map) {
for(List<Integer> l : all){
String out = "";
for (int i = 0; i < l.size(); i++) {
out += map.get(l.get(i));
}
System.out.println(out);
}
}

private static void rec(List<Integer> l, List<List<Integer>> all) {
for (int i = 0; i < l.size(); i++) {
if(i+1 < l.size() && l.get(i) < 9 && l.get(i+1) < 9){
int n = l.get(i) * 10 + l.get(i+1);
if(n<26){
List<Integer> lnew = new ArrayList<>(l);
lnew.remove(i+1);
lnew.set(i, n);
rec(lnew, all);
}
}
}
}

private static List<Integer> prepareList(char[] a) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < a.length; i++) {
}
return list;
}

private static void fill(Map<Integer, Character> map) {
char c;
for(int i =0 ; i < 26; i++){
c = (char) ('a' + i);
map.put(i+1 , c);
}
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

javascript solution with DP

``````function charOf(number) {
number = parseInt(number);
if (number > 0 && number < 27) {
let begin = 'a'.charCodeAt(0) - 1;
return String.fromCharCode(begin + parseInt(number));
}
return '';
}
function findPatterns(str) {
let cache = {};

function patterns(substring) {
if (substring == '') return [];

if (cache[substring]) return cache[substring];
if (substring.length === 1 && substring > 0) {
cache[substring] = [charOf(substring)];
return cache[substring];
}

let one = patterns(substring.slice(1))
.map(e => charOf(substring[0]) + e);

let two = [];
if ( substring.substring(0, 2) < 27 ) {

let prefix = charOf(substring.substring(0, 2));
two = patterns(substring.slice(2))
.map(e => prefix + e);
if (two.length === 0) two.push(prefix);
}
cache[substring] = Array.from(new Set([...one, ...two]));
return cache[substring];
}

let p = patterns(str);
console.log(cache);
return [p, p.length];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Best to just memoize and not try to do anything fancier.

``````function toCode(s : string, k : number) : number {
let c = parseInt(s[k]);
if (c == 0)
throw new Error();
assert(c >= 1 && c <= 9);
return c;
}
function fromCode(c : number) {
assert(c >= 1 && c <= 26);
return String.fromCharCode("a".toCharCode(0) + c - 1);
}

function allCode(s : string, k : number, map : Map<number,string[]>) : string[] {
if (k == s.length)
return [""];
if (map.has(k))
return map.get(k);
let c0 = toCode(s, k);
let l0 = fromCode(c0);
let restA = allCode(s, k + 1, map);
let result = restA.map(s => l0 + s);
if (k + 1 < s.length) {
let c1 = toCode(s, k + 1);
let c01 = (c0 * 10) + c1;
(c01 >= 1).assert();
if (c01 <= 26) {
let l01 = fromCode(c01);
let restB = allCode(s, k + 2, map);
result.push(...restB.map(s => l01 + s));
}
}
map.set(k, ret);
return ret;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

My code in C, linear time and space

``````#include<stdio.h>
#define MAX_SIZE 100 //Maximum input size

//returns true if current number be coupled with previous
inline int couple(int i, char inp[MAX_SIZE+1])
{
if(i<1)
return 0;
if(inp[i-1] == '1')
return 1;
if(inp[i-1] == '2' && inp[i] < '7')
return 1;
return 0;
}

//calculate number of ways
int calculate(char inp[MAX_SIZE+1])
{
int a1 = 1, a2=1, a3=1;
int i;
for(i=0; inp[i]!='\0'; i++){
if(couple(i, inp))
a1 = a2 + a3;
else
a1 = a2;
a3 = a2;
a2 = a1;
}
return a1;
}

int main(void)
{
char inp[MAX_SIZE+1];
scanf("%s", inp);
printf("%d\n", calculate(inp));
}

int calculate(char inp[MAX_SIZE], int size)
{
int a_n3 = 1, a_n1=1, a_n2=0;
int i;
for(int i=0; i<size; i++){
if(couple(i, inp, size))
a_n3 = a_n1 + a_n2;
else
a_n3 = a_n1;
a_n1 = a_n2;
a_n2 = a_n3;
}
return a_n3;
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

``````def generate(num):
if num < 1: return ['']
if num <= 10: return [str(chr(96 + num))]

first_two, mag = num, 1
while first_two > 99:
first_two /= 10
mag *= 10

res = []
if first_two <= 26:
for s in generate(num - ((first_two // 10) * mag * 10)):
res.append(chr(96 + first_two//10) + s)

for s in generate(num - (first_two * mag)):
res.append(chr(96 + first_two) + s)
return res``````

Comment hidden because of low score. Click to expand.
-2
of 2 vote

By using recursion: From each position we move by 1 and then by 2 positions:

``````package facebook;

public class GenerateAlphaCode {

public static char[] 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' };

public static void main(String[] args) {

generateString("1123", new StringBuilder(), 0);
}

public static void generateString(String nums, StringBuilder sb, int pos) {

if (pos > nums.length()) {
return;
}
if (pos == nums.length()) {
System.out.println(sb);
return;
}

sb.append(ALPHABET[Integer.parseInt(nums.substring(pos, pos + 1))]);
generateString(nums, sb, pos + 1);
sb.setLength(sb.length() - 1);

if (pos + 2 <= nums.length()) {
sb.append(ALPHABET[Integer.parseInt(nums.substring(pos, pos + 2))]);
generateString(nums, sb, pos + 2);
sb.setLength(sb.length() - 1);
}
}
}``````

Comment hidden because of low score. Click to expand.
0

Thank you

Comment hidden because of low score. Click to expand.
-2
of 2 vote

``````class Decode {
private static char[] alpha =
{ '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' };
private static int[] B = { 1, 2, 3, 1, 2, 3 };

public static void print(int[] A) {
int n;
String s = "";
for (int i = 0; i < A.length; i++) {
if (A[i] == 1)
s += alpha[B[i] - 1];
if (A[i] == 2) {
n = (B[i] * 10) + B[i + 1];
if (n < 27)
s += alpha[n - 1];
else
return; // don't print the string as it had an invalid alphabet
i++;
}
}
System.out.println(s);
}

public static void combination(int[] A, int k, int n) {
if (k == n)  print(A);
else {
A[k] = 1;
combination(A, k + 1, n);
A[k] = 2;
if (k + 2 > n)  return;
combination(A, k + 2, n);
}
}

public static void main(String args[]) {
int n = B.length;
int[] A = new int[n];
combination(A, 0, n);
}
}``````

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

May be if the input contains 0 you need to check for the same

``````if (A[i] == 1) {
if (B[i] - 1 < 0) return;    <===
s += alpha[B[i] - 1];
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.