Facebook Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
@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.
@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;
}
@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.
@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)) )
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;
}
result.add(str);
return result;
}
else
{
int charCode = Integer.valueOf(in.charAt(charAt) + "");
char curChar = numberToChar.get(charCode);
arrayList.add(curChar);
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.add(curChar);
result.addAll(decodeHelper(numberToChar, in, charAt+2, arrayList));
arrayList.remove(arrayList.size()-1);
}
}
}
return result;
}
}
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.
@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;
}
result.add(str);
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);
arrayList.add(curChar);
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.add(curChar);
result.addAll(decodeHelper(numberToChar, in, charAt + 2,
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
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);
temp1 = addChrToPrefix(preRet, chr);
}
}
int val = Integer.valueOf(string.substring(index, index + 1));
if (val != 0){
char chr = (char)(val + 96);
temp2 = addChrToPrefix(ret, chr);
}
preRet = ret;
temp1.addAll(temp2);
ret = temp1;
}
return ret;
}
private static List<String> addChrToPrefix(List<String> preRet, char chr) {
List<String> ret = new ArrayList<String>();
if (preRet.size() == 0){
ret.add(String.valueOf(chr));
}
for (String item : preRet){
ret.add(item + String.valueOf(chr));
}
return ret;
}
}
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));
}
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 :-)
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?
@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?
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)
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)
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)
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;
}
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);
}
It doesn't work for this input: "101523"
Output list cannot contain a. It must start with j since 10=a. But pretty close.
@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);
}
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);
}
}
}
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]])
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.
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);
}
#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;
}
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');
#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;
}
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;
}
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
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);
}
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]);
#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);} }
}
}
}
}
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;
}
{
class FacebookQ1
{
public static void GetInterpretationCount(int[] l)
{
Node head = new Node();
AddChild(head, 0, l);
int x = FindCount(head);
}
static void AddChild(Node n, int pos, int[] l)
{
if (pos < l.Length)
{
char y = (char)(l[pos] + 64);
n.left = new Node(y);
AddChild(n.left, pos + 1, l);
if (pos + 1 < l.Length)
{
int x = l[pos] * 10 + l[pos + 1];
if (x <= 26)
{
n.right = new Node((char)(x + 64));
AddChild(n.right, pos + 2, l);
}
}
}
}
private static int FindCount(Node head)
{
int x = 0; int y = 0;
if (head.left != null)
{
x += FindCount(head.left);
}
if (head.right != null)
{
y += FindCount(head.right);
}
if (head.right == null && head.left == null)
{
return 1;
}
return x + y;
}
}
class Node
{
public Node()
{
}
public Node(char x)
{
c = x;
}
public char c;
public Node left;
public Node right;
}
}
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;
}
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;
}
}
}
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) {
strings.add(output);
} else if (len == 1) {
strings.add(output + codes[Integer.parseInt(input)]);
} 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);
}
}
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;
}
if (found) result.add(currentWord);
}
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) {
result.add(value);
value = getNextCombination(value);
}
}
return result;
}
private static ArrayList<Integer> getNextCombination(ArrayList<Integer> values) {
int i;
ArrayList<Integer> result = new ArrayList<Integer>();
result.addAll(values);
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);
}
}
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)
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']
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");
}
}
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);
}
}
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();
}
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;
}
#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;
}
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');
}}
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);
}
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
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;
}
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;
}
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)
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) {
values.add(base);
}
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
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);
Console.Read();
}
}
}
#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;
}
/// 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;
}
/**
* 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));
}
}
{{using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
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");
Console.ReadKey();
}
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));
}
}
}
}
}
}}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
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");
Console.ReadKey();
}
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));
}
}
}
}
}
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));
}
}
}
#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();
}
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);
}
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{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Give the input:");
input = bf.readLine();
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){
str.add(ans);
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);
}
}
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
#
#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;
}
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;
}
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', '')
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()
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;
}
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'))));
}
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'))));
}
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]
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]
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)
#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;
}
//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);
}())
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;
}
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 {
[rtArray addObject:currentString];
}
}
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
)
public Set<String> decode(String prefix , String code){
Set<String> set = new HashSet<String>();
if(code.length() == 0){
set.add(prefix);
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;
}
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;
}
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));
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.
*/
@property (nonatomic, readonly) NSSet *results;
/**
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) {
[self.parsed addObject:prefix];
}
}
- (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
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 = @""; });
it(@"produces no results", ^{
[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
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)
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
}
}
#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;
}
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]);
}
}
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]);
}
}
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)
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){
combos.add(code + subCombo);
}
}
return combos;
}
}
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);
result.add(codedChar);
decode(word, k+prefix.length(),n);
result.remove(result.size()-1);
}
}
}
decode("1123",0,"1123".length());
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);
result.add(codedChar);
decode(word, k+prefix.length(),n);
result.remove(result.size()-1);
}
}
}
decode("1123",0,"1123".length());
#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;
}
#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;
}
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:])
# start with empty
next('', list(user_input))
print combinations
#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;
}
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))
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))
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.
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) {
allPerms.add(currentList);
return;
}
if (s.length() == 1) {
currentList.add(getEncodedString(charsMap, s.substring(0, 1)));
allPerms.add(currentList);
return;
}
List<String> copy = new ArrayList<>(currentList);
copy.add(charsMap.get(Integer.parseInt(s.substring(0, 1))));
getValidLists(charsMap, s.substring(1), allPerms, copy);
String subString = s.substring(0, 2);
if (Integer.parseInt(subString) <= 26) {
currentList.add(getEncodedString(charsMap, subString));
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);
}
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]);
return [takeTwo arrayByAddingObjectsFromArray:takeOne];
}
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSArray* perms = numberPermutations(112334054, @"");
for (NSString* perm in perms) {
NSLog(@"%@", perm);
}
}
return 0;
}
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) {
strArr.add(hm.get(str));
} else if (str.length() == 2) {
strArr.add(hm.get("" + str.charAt(0)) + hm.get("" + str.charAt(1)));
if (Integer.parseInt(str) <= 26) {
strArr.add(hm.get(str));
}
} 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++) {
strArr.add(hm.get(firstChar) + lst.get(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++) {
strArr.add(hm.get(firstTwoChars) + lst.get(i));
}
}
}
return strArr;
}
/* 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,'')
/* 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 )
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, '')
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, '')
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, '')
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))
_CodesDic.Add(code, res);
return res;
}
#!/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
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)
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)
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")
-- 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
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 class FacebookFlipkartQuestion {
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);
all.add(l);
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);
all.add(lnew);
rec(lnew, all);
}
}
}
}
private static List<Integer> prepareList(char[] a) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < a.length; i++) {
list.add(Character.getNumericValue(a[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);
}
}
}
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 class FacebookFlipkartQuestion {
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);
all.add(l);
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);
all.add(lnew);
rec(lnew, all);
}
}
}
}
private static List<Integer> prepareList(char[] a) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < a.length; i++) {
list.add(Character.getNumericValue(a[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);
}
}
}
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];
}
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;
}
public static void helper_getCode(String input, String codeSoFar, List<String> ans) {
int a = ((int) 'a') - 1;
// Base Case:
if (input == null) {
return;
}
if (input.length() == 0) {
ans.add(codeSoFar);
return;
}
String subInput = "";
String first_ch = "";
if (input.length() >= 2) {
first_ch = input.substring(0, 2);
if ((Integer.parseInt(first_ch) >= 10) && (Integer.parseInt(first_ch) <= 26)) {
subInput = input.replaceFirst(first_ch, "");
helper_getCode(subInput, (codeSoFar + (char) (a + Integer.parseInt(first_ch))), ans);
}
}
if (input.length() >= 1) {
first_ch = input.substring(0, 1);
subInput = input.replaceFirst(first_ch, "");
helper_getCode(subInput, (codeSoFar + (char) (a + Integer.parseInt(first_ch))), ans);
}
}
public static void helper_getCode(String input, String codeSoFar, List<String> ans) {
int a = ((int) 'a') - 1;
// Base Case:
if (input == null) {
return;
}
if (input.length() == 0) {
ans.add(codeSoFar);
return;
}
String subInput = "";
String first_ch = "";
if (input.length() >= 2) {
first_ch = input.substring(0, 2);
if ((Integer.parseInt(first_ch) >= 10) && (Integer.parseInt(first_ch) <= 26)) {
subInput = input.replaceFirst(first_ch, "");
helper_getCode(subInput, (codeSoFar + (char) (a + Integer.parseInt(first_ch))), ans);
}
}
if (input.length() >= 1) {
first_ch = input.substring(0, 1);
subInput = input.replaceFirst(first_ch, "");
helper_getCode(subInput, (codeSoFar + (char) (a + Integer.parseInt(first_ch))), ans);
}
}}
public static void helper_getCode(String input, String codeSoFar, List<String> ans) {
int a = ((int) 'a') - 1;
// Base Case:
if (input == null) {
return;
}
if (input.length() == 0) {
ans.add(codeSoFar);
return;
}
String subInput = "";
String first_ch = "";
if (input.length() >= 2) {
first_ch = input.substring(0, 2);
if ((Integer.parseInt(first_ch) >= 10) && (Integer.parseInt(first_ch) <= 26)) {
subInput = input.replaceFirst(first_ch, "");
helper_getCode(subInput, (codeSoFar + (char) (a + Integer.parseInt(first_ch))), ans);
}
}
if (input.length() >= 1) {
first_ch = input.substring(0, 1);
subInput = input.replaceFirst(first_ch, "");
helper_getCode(subInput, (codeSoFar + (char) (a + Integer.parseInt(first_ch))), ans);
}
}
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;
}
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
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);
}
}
}
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);
}
}
call
decode("", "1123");
- Antonio081014 July 24, 2013public Set<String> decode(String prefix, String code) { Set<String> set = new HashSet<String>(); if (code.length() == 0) { set.add(prefix); 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') { set.addAll(decode( prefix + (char) (10 + code.charAt(1) - '1' + 'a'), code.substring(2))); } if (code.length() >= 2 && code.charAt(0) == '2' && code.charAt(1) <= '6') { set.addAll(decode( prefix + (char) (20 + code.charAt(1) - '1' + 'a'), code.substring(2))); } return set; }