Facebook Interview Question Software Engineers
Country: United States
Interview Type: In-Person
Sorry, career cup is breaking down on me and it's super frustrating; I've been having difficulty editing my comment. Here's the corrected version of my comment:
You can solve this problem by breaking down your input string into subproblems based on the first two characters of your input string. The resultant count is the number of leaves in your recursion.
For instance.
You break up the solution to "123" into these subproblems:
solution("123")
-> "1" + solution("23")
-> "1" + "2" + solution("3") => "1,2,3"
-> "1" + "23" + solution("") => "1", "23"
-> "12" + solution("3") => "12", "3"
To capture this, here's some simple Java code which shows this idea and also prints out each possible solution so you can easily confirm that the solution is correct.
public static int findHowManyStrings(String soFar, String numberString, String rest) {
final String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
if (rest.length() == 0) {
System.out.println(soFar + "=" + numberString);
return 1;
} else if (rest.length() == 1) {
System.out.println(soFar + ALPHABET.charAt(Integer.parseInt(rest)-1) + "=" + numberString + rest);
return 1;
} else {
int sum = findHowManyStrings(soFar + ALPHABET.charAt(Integer.parseInt(rest.substring(0, 1))-1) + ",", numberString + rest.substring(0, 1) + ",", rest.substring(1));
String firstTwo = rest.substring(0, 2);
if (Integer.parseInt(firstTwo) <= 26) {
sum += findHowManyStrings(soFar + ALPHABET.charAt(Integer.parseInt(firstTwo)-1) + ",", numberString + rest.substring(0,2) + ",", rest.substring(2));
}
return sum;
}
}
bool isValid(string s){
istringstream ibuf(s);
int num;
ibuf >> num;
if(num>=1 && num <=26)
return true;
else
return false;
}
int numEncoding(string s){
if(s.length()==0) return 1;
if(s.length()==1) return 1;
int num = 0;
num += numEncoding(s.substr(1));
if(isValid(s.substr(0,2)))
num += numEncoding(s.substr(2));
return num;
}
for input 11111, there are 8 combinations
{1,1,1,1,1}, {11,1,1,1},{1,11,1,1}, {1,1,11,1},{1,1,1,11}, {1,11,11}, {11,1,11}, {11,11,1}
here is my program
int findDecodeCombinationCount(char *string){
if(*string == '\0'){
return 1;
} else if(*string <= '0' || *string > '9'){
printf("DECODE ERROR, invalid input !!\n");
return 0;
} else if(*(string+1) == '\0') {
return 1;
} else if (*(string+1) == '0'){
return findDecodeCombinationCount(string+2) ;
} else if((*string > '2') || ((*string == '2') && (*(string+1) > '6'))){
return findDecodeCombinationCount(string+1) ;
} else {
return findDecodeCombinationCount(string+1) + findDecodeCombinationCount(string+2);
}
}
/* The brute-force approach involves using recursion without any caching and takes exponential time.
A more optimal approach is using an approach similar to calculating fibonacci (just store the previous 2 results) and compute the current results.
This takes O(N^2) time where N i the length of the string. The space is also O(N^2). */
public ArrayList<String> encodings(String s)
{
if(s==null||s.length()==0||s.charAt(0)=='0')
{
return Collections.<String>emptyList();
}
ArrayList<ArrayList<Integer>> i_2=new ArrayList<ArrayList<Integer>>();
ArrayList<ArrayList<Integer>> i_1=new ArrayList<ArrayList<Integer>>();
i_1.add("" + s.charAt(0));
for(int i=1;i<s.length();i++)
{
int d1=s.charAt(i-1)-'0';
int d2=s.charAt(i)-'0';
d1=(d1*10)+d2;
ArrayList<ArrayList<Integer>> tmp=new ArrayList<ArrayList<Integer>>();
//if one digit combination is valid (between 1-26 and not equal to 2 digit combination)
if((d2>=1 && d2<=26) && d1!=d2))
{
tmp.addAll(append(i_2,d2));
}
//if two digit combination is valid (between 1-26 and not equal to 1 digit combinaton)
if((d1>=1 && d1<=26) && d1!=d2))
{
tmp.addAll(append(i_1,d1));
}
i_2=i_1;
i_1=tmp;
}
}
private ArrayList<ArrayList<Integer>> append(ArrayList<ArrayList<Integer>> ls, int d)
{
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
for(ArrayList<Integer> l:ls)
{
ArrayList<Integer> x=new ArrayList<Integer>(l);
x.add(d);
result.add(x);
}
return result;
}
Following is the recursive solution, One can easily derive DP solution.
Please comment if there is any mistake.
Thanks.
Srinu
#include <iostream>
#include <string>
using namespace std;
int solRec(string str, int low, int high) {
string str1,str2;
str1 = str.substr(low,1);
str2 = str.substr(low,2);
int first = atoi(str1.c_str());
int second = atoi(str2.c_str());
if(low == high) return 1;
if(low+1 == high && second < 27) return 2;
if(low+1 == high && second > 26) return 1;
int res = 0, ret1 = 0, ret2 = 0;
ret1 = solRec(str, low+1, high);
if(second<27)
ret2 = solRec(str, low+2, high);
res = ret1 + ret2;
return res;
}
int main() {
string str;
cin>>str;
int len = str.length();
cout<<solRec(str,0,len-1)<<endl;
return 0;
}
class WordEncrypt {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String number = sc.next();
int[] numbers = new int[number.length()];
int num = Integer.parseInt(number);
for(int i=number.length() - 1; i > -1 ; i--) {
numbers[i] = num % 10;
num = num/10;
}
WordEncrypt we = new WordEncrypt();
ArrayList<LinkedList<Integer>> result = we.findWordCombination(numbers, 0);
we.printResult(result);
}
public void printResult(ArrayList<LinkedList<Integer>> result) {
for(int i=0; i < result.size(); i++) {
LinkedList<Integer> list = result.get(i);
while(!list.isEmpty()) {
System.out.print(list.pollFirst() + ", ");
}
System.out.println();
}
}
ArrayList<LinkedList<Integer>> findWordCombination(int[] numbers, int index) {
ArrayList<LinkedList<Integer>> result = new ArrayList<LinkedList<Integer>>();
if(index == numbers.length -1 ) {
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(numbers[index]);
result.add(list);
return result;
}
ArrayList<LinkedList<Integer>> tempresult = findWordCombination(numbers, index+1);
for(int i = 0; i < tempresult.size(); i++) {
LinkedList<Integer> firstlist = new LinkedList<Integer>();
firstlist.addAll(tempresult.get(i));
int character = Integer.parseInt(numbers[index] + "" + firstlist.getFirst());
firstlist.addFirst(numbers[index]);
result.add(firstlist);
if(character < 27 && character > 9) {
LinkedList<Integer> secondlist = new LinkedList<Integer>();
secondlist.addAll(tempresult.get(i));
Integer head = secondlist.pollFirst();
secondlist.addFirst(Integer.parseInt(numbers[index] +""+ head));
result.add(secondlist);
}
}
return result;
}
}
def nCombs(s):
if len(s) < 2:
return 1
else: # len(s) > 1
ac = nCombs(s[1:])
if s[0] == '0':
return ac
if int(s[:2]) <= 26 and int(s[:2]) > 0:
ac += nCombs(s[2:])
return ac
def nEncodings(s):
print("nEncodings(", s, "):", nCombs(s))
nEncodings("123")
nEncodings("1234")
nEncodings("111")
nEncodings("1111")
nEncodings("11111")
def nCombs(s):
if len(s) < 2:
return 1
else: # len(s) > 1
ac = nCombs(s[1:])
if s[0] == '0':
return ac
if int(s[:2]) <= 26 and int(s[:2]) > 0:
ac += nCombs(s[2:])
return ac
def nEncodings(s):
print("nEncodings(", s, "):", nCombs(s))
nEncodings("123")
nEncodings("1234")
nEncodings("111")
nEncodings("1111")
nEncodings("11111")
As some of contributors pointed out, the is a typical dynamic problem. The sub-problem is easy to spot as well. The key here is it might have 0, 1 or 2 sub-problems depending on its current value and its subsequent value. For instance string starting with 0, "0......", does not have any sub-problem, "28......" has 1 sub-problem and string "12......" has 2 sub-problems.
Details: cpluspluslearning-petert.blogspot.co.uk/2016/06/dynamic-programming-string-decoder.html
Test
void TestDecoder()
{
assert(StringDecoder("134a457") < 0);
assert(StringDecoder("100") < 0);
assert(StringDecoder("12") == 2);
assert(StringDecoder("123") == 3);
assert(StringDecoder("0123456789") < 0);
assert(StringDecoder("10123") == 3);
assert(StringDecoder("345") == 1);
assert(StringDecoder("1123") == 5);
assert(StringDecoder("5123") == 3);
}
class Encode:
def __init__(self):
self.ecoding = {}
self.__init_dict()
def __init_dict(self):
for i in range(1,27):
self.ecoding[str(i)] = chr(ord('a') + i -1)
print self.ecoding
def generate_all_encoding(self, input):
result = []
partial = ""
self.__generate_all_encoding(input.lower() , result, partial)
return result
def __generate_all_encoding(self, input, result, partial):
if input == "":
result.append(partial)
return
for i in range(1,3):
if len(input) >= i:
prefix = input[:i]
if self.ecoding.has_key(prefix):
self.__generate_all_encoding(input[i:], result, partial+self.ecoding[prefix])
package consumer;
/**
* Created by tiwariaa on 6/14/2016.
*/
public class CharFromStringCombination {
public boolean validateWithInInputRange(char c) {
return ('a' <= c && c <= 'z');
}
public char getCharFromInt(int i) {
int val = 'a';
val = val + (i - 1);
return (char) val;
}
public int getIntValueFromChar(char c) {
int charVal = c;
int charValA = 'a';
return charVal - charValA + 1;
}
public String[] process(String input) {
String[] output = new String[input.length()];
for (int i = 0; i < input.length(); i++) {
String toAdd = "";
if (i + 1 < input.length()) {
int char1 = getIntValueFromChar(input.charAt(i));
int char2 = getIntValueFromChar(input.charAt(i + 1));
String totalChar = char1 + "" + char2;
char newChar = getCharFromInt(Integer.parseInt(totalChar));
if (validateWithInInputRange(newChar)) {
toAdd = input.substring(0, i) + Character.toString(newChar) + input.substring(i + 2);
output[i] = toAdd;
}
} else {
continue;
}
}
return output;
}
public static void main(String[] args) {
CharFromStringCombination charFromStringCombination = new CharFromStringCombination();
for (String str : charFromStringCombination.process("abc")) {
if (str != null)
System.out.println(str);
}
}
}
I also used divide and conquer and dynamic programming here.
I've implemented it recursively just because I love it's simplicity and the solution should run in O(N) space and time so, unless we're dealing with a long string, it should work fine.
I have separated the dynamic programming solution from the divide and conquer approach in 2 functions (one being a cache decorator).
# Yes, this is Python
def cache(func):
cache = {}
def wrapper(value):
if value in cache:
print 'cache hit: %s (%d)' % (value, len(cache))
return cache[value]
else:
count = func(value)
cache[value] = count
print 'cache miss: %s (%d)' % (value, len(cache))
return count
wrapper.__name__ = func.__name__
return wrapper
@cache
def count_encodings(value):
if len(value) < 2:
return 1
z = 26
count = count_encodings(value[1:])
# if the first 2 digits can encode a letter
if int(value[:2]) <= z:
count += count_encodings(value[2:])
return count
The problem is much more simpler than some of the solutions.
Since we only have english alphabets whose encoded space is between 1 and 26.
The only time there is an ambiguity in decoding is when the character is 1 or 2.
The other special case is 0.
Here is a sample code.// No validations done
public int totalNumofDecodes(int [] array) {
int count = 1;
for(int i=0; i< array.length; i++) {
if(array[i] == 0) count--;
if(array[i] == 1) count++;
if(array[i] == 2 && i<array.length-1 && array[i+1] <= 6) count++;
}
return count;
}
Solved by dividing the problems into sub-problems of smaller size.
But I am not caching any intermediate results.
That might fasten the algorithm.
public class Main {
public static void main(String[] args) {
//String s = "1234"; //3
//String s = "5555"; //1
String s = "11111"; //8
System.out.println("Number of possible decodes : "+countOfPossibleDecodes(s));
}
public static int countOfPossibleDecodes(String s){
int count=0;
if(s.length()==1){
return 1;
}
if(s.length()==0){
return 1;
}
count = countOfPossibleDecodes(s.substring(1));
if(s.charAt(0)=='1'){
count += countOfPossibleDecodes(s.substring(2));
}
if(s.charAt(0)=='2' && s.charAt(1)<='6'){
count += countOfPossibleDecodes(s.substring(2));
}
return count;
}
}
void decode_and_print(const char* code, char *decode, int idx)
{
int len = 0;
int offset = 'a' - 1;
char code_str[3];
len = strlen(code);
if (len == 0) {
decode[idx] = '\0';
printf("%s\n", decode);
return;
}
code_str[2] = '\0';
code_str[1] = '\0';
code_str[0] = code[0];
decode[idx] = (char)(atoi(code_str) + offset);
decode_and_print(&code[1], decode, idx + 1);
if (len > 1) {
code_str[1] = code[1];
decode[idx] = (char)(atoi(code_str) + offset);
decode_and_print(&code[2], decode, idx + 1);
}
}
void decode(const char *code)
{
int len = 0;
char *decoded_string;
decoded_string = (char *)malloc(strlen(code) + 1);
decode_and_print(code, decoded_string, 0);
free(decoded_string);
}
Since the question is only asking the number of possible translations, a simple Python solution using dynamic programming goes as follows:
def decode_number(array):
if array[0] == 0:
return 0
alpha = 26
# Lead with an extra zero
tab = [0] * len(array)
tab[0] = 1
for i in range(1, len(array)):
n = array[i]
if n == 0:
# Zero is special as it must
# combine with its predecessor
if array[i-1] * 10 + n > alpha:
return 0
tab[i] = tab[i-1]
if array[i-1] * 10 + n <= alpha:
tab[i] += 1
return tab[-1]
Both Recursive and DP Solution
public class NumberofDecodedNumber {
public static int dpSolution(char a[]) {
int f0=1;
int f1=1;
int res=0;
int length = 2;
for (; length < a.length; length++) {
res=f1;
if ( a[length-2] <= '2' && a[length-1] <= '6') {
res+=f0;
}
f0=f1;
f1=res;
}
return res;
}
public static int recSolution(String s) {
char a[] = s.toCharArray();
return recSolution(a, 0);
}
private static int recSolution(char a[], int length) {
boolean flag = false;
if (length == a.length - 1)
return 1;
if (length > a.length)
return 0;
if (length < (a.length - 1) && a[length] <= '2' && a[length + 1] <= '6') {
flag = true;
}
return recSolution(a, length + 1) + (flag == true ? recSolution(a, length + 2) : 0);
}
public static void main(String[] args) {
String s = "122121342424241212253";
System.out.println(recSolution(s));
System.out.println(dpSolution(s.toCharArray()));
}
}
I used a list but you can use Queue and dequeue head and add to result if you like.
public class Decode {
public static void main(String[] args) {
printResult(crazySolution("12"));
printResult(crazySolution("123"));
printResult(crazySolution("1234"));
printResult(crazySolution("11111"));
printResult(crazySolution("111111"));
}
private static List<Combo> crazySolution(String input){
List<Combo> result = new ArrayList<Combo>();
//TODO check for null or input length
//Add initial input as list
Combo combo = new Combo(0, Arrays.asList(input.split("")));
result.add(combo);
//Continues loop on result list
for( int j= 0; j < result.size(); j++){
List<String> nums = result.get(j).getPermutation();
for(int i = result.get(j).getIndex() ; i < nums.size() - 1; i++) {
int num = Integer.parseInt(nums.get(i) + "" + nums.get(i + 1));
if (num > 0 && num <= 26) {
List<String> list = new ArrayList<String>();
if( i > 0) {
list.addAll(nums.subList(0, i));
}
list.add(num + "");
list.addAll(nums.subList(i+2, nums.size()));
// add to result with Index to start from
result.add(new Combo(i + 1, list));
}
}
}
return result;
}
private static void printResult(List<Combo> result) {
System.out.println("Size :" + result.size());
for(Combo combo : result){
dump(combo.getPermutation());
}
}
private static void dump(List<String> list){
for(String str : list) {
System.out.print(str + ", ");
}
System.out.println(" ");
}
//Helper java pojo to preserve index.
class Combo{
int index;
List<String> permutation;
public Combo(int index, List<String> permutation) {
this.index = index;
this.permutation = permutation;
}
public List<String> getPermutation() {
return permutation;
}
public int getIndex() {
return index;
}
}
OutPut :
Size :2
1, 2,
12,
Size :3
1, 2, 3,
12, 3,
1, 23,
Size :3
1, 2, 3, 4,
12, 3, 4,
1, 23, 4,
Size :8
1, 1, 1, 1, 1,
11, 1, 1, 1,
1, 11, 1, 1,
1, 1, 11, 1,
1, 1, 1, 11,
11, 11, 1,
11, 1, 11,
1, 11, 11,
Size :13
1, 1, 1, 1, 1, 1,
11, 1, 1, 1, 1,
1, 11, 1, 1, 1,
1, 1, 11, 1, 1,
1, 1, 1, 11, 1,
1, 1, 1, 1, 11,
11, 11, 1, 1,
11, 1, 11, 1,
11, 1, 1, 11,
1, 11, 11, 1,
1, 11, 1, 11,
1, 1, 11, 11,
11, 11, 11,
Ok, my stupid crazy solution also prints all combination. You can use queue and dequeu head to result list but I just used a List.
public class Decode {
public static void main(String[] args) {
printResult(crazySolution("12"));
printResult(crazySolution("123"));
printResult(crazySolution("1234"));
printResult(crazySolution("11111"));
printResult(crazySolution("111111"));
}
private static List<Combo> crazySolution(String input){
System.out.println("Input :" + input);
List<Combo> result = new ArrayList<Combo>();
//TODO check for null or input length
//Add initial input as list
Combo combo = new Combo(0, Arrays.asList(input.split("")));
result.add(combo);
//Continues loop on result list
for( int j= 0; j < result.size(); j++){
List<String> nums = result.get(j).getPermutation();
for(int i = result.get(j).getIndex() ; i < nums.size() - 1; i++) {
int num = Integer.parseInt(nums.get(i) + "" + nums.get(i + 1));
if (num > 0 && num <= 26) {
List<String> list = new ArrayList<String>();
if( i > 0) {
list.addAll(nums.subList(0, i));
}
list.add(num + "");
list.addAll(nums.subList(i+2, nums.size()));
// add to result with Index to start from
result.add(new Combo(i + 1, list));
}
}
}
return result;
}
private static void printResult(List<Combo> result) {
System.out.println("Result count :" + result.size());
for(Combo combo : result){
dump(combo.getPermutation());
}
}
private static void dump(List<String> list){
for(String str : list) {
System.out.print(str + ", ");
}
System.out.println(" ");
}
}
//Helper java pojo
class Combo{
int index;
List<String> permutation;
public Combo(int index, List<String> permutation) {
this.index = index;
this.permutation = permutation;
}
public List<String> getPermutation() {
return permutation;
}
public int getIndex() {
return index;
}
}
Output -------
Input :12
Result count :2
1, 2,
12,
Input :123
Result count :3
1, 2, 3,
12, 3,
1, 23,
Input :1234
Result count :3
1, 2, 3, 4,
12, 3, 4,
1, 23, 4,
Input :11111
Result count :8
1, 1, 1, 1, 1,
11, 1, 1, 1,
1, 11, 1, 1,
1, 1, 11, 1,
1, 1, 1, 11,
11, 11, 1,
11, 1, 11,
1, 11, 11,
Input :111111
Result count :13
1, 1, 1, 1, 1, 1,
11, 1, 1, 1, 1,
1, 11, 1, 1, 1,
1, 1, 11, 1, 1,
1, 1, 1, 11, 1,
1, 1, 1, 1, 11,
11, 11, 1, 1,
11, 1, 11, 1,
11, 1, 1, 11,
1, 11, 11, 1,
1, 11, 1, 11,
1, 1, 11, 11,
11, 11, 11,
I was able to get O(N) runtime
import java.util.Dictionary;
import java.util.Hashtable;
public class WordCombination {
public static void main(String[] args) {
long startTime = System.nanoTime();
System.out.println(new WordCombination().numEncoding("255156181465896518965139846518564115881623848947651321856468513215631856413651321847897794137971894654734768151128"));
long endTime = System.nanoTime();
System.out.println("Took "+(endTime - startTime)/1000000 + " ms");
}
boolean isValid(String s){
int num = Integer.parseInt(s);
if(num>=1 && num <=26)
return true;
else
return false;
}
public int numEncoding(String s, Dictionary<String, Integer> memory) {
if(s.length()==0) return 1;
if(s.length()==1) return 1;
int num = 0;
String s1 = s.substring(1);
int s1Num;
if(memory.get(s1) != null) {
s1Num = memory.get(s1);
} else {
s1Num = numEncoding(s1, memory);
memory.put(s1, s1Num);
}
num += s1Num;
if(isValid(s.substring(0, 2))) {
String s2 = s.substring(2);
int s2Num;
if(memory.get(s2) != null) {
s2Num = memory.get(s2);
} else {
s2Num = numEncoding(s2, memory);
memory.put(s2, s2Num);
}
num += s2Num;
}
return num;
}
private int numEncoding(String s){
Hashtable<String, Integer> memory = new Hashtable<String, Integer>();
return numEncoding(s, memory);
}
}
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
int decode(int res[], int index, int size){
if ( index == size - 1)
return 1;
else if( index == size - 2)
return 2;
else
{
if (res[index] <= 2 && res[index+1] <= 6){
return decode(res, index+1, size) + decode(res, index+2, size);
} else if(res[index] > 2){
return decode(res, index+1, size);
} else {
return decode(res, index+1, size);
}
}
}
int main(int argc, char *argv[]){
int res[2*strlen(argv[1])];
int index = 0;
printf("%s\n", argv[1]);
for(int i=0;i<strlen(argv[1]);i++){
int tmp = 0;
printf("%d", tmp = (tolower(argv[1][i]) - 'a' + 1));
if (tmp < 10){
res[index] = tmp;
index++;
} else {
res[index++] = tmp / 10;
res[index++] = tmp % 10;
}
}
res[index] = 0;
int total = decode (res, 0, index);
printf("Total combinations: %d\n", total);
return 0;
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSString* str = @"11111";
int num = 1;
int numPrev = 1;
for(int i = 1; i <str.length; i++){
int numOld = num;
if([str characterAtIndex:i] != '0'){
NSString* substr = [str substringWithRange:NSMakeRange(i-1, 2)];
int subsStrValue = [substr intValue];
if(subsStrValue <=26){
num = num + numPrev;
}
}
numPrev = numOld;
}
NSLog(@"%d", num);
}
return 0;
}
int main(int argc, const char * argv[]) {
@autoreleasepool {
NSString* str = @"11111";
int num = 1;
int numPrev = 1;
for(int i = 1; i <str.length; i++){
int numOld = num;
if([str characterAtIndex:i] != '0'){
NSString* substr = [str substringWithRange:NSMakeRange(i-1, 2)];
int subsStrValue = [substr intValue];
if(subsStrValue <=26){
num = num + numPrev;
}
}
numPrev = numOld;
}
NSLog(@"%d", num);
}
return 0;
}
extension String {
func permutations() -> Int {
let len = self.characters.count
guard len > 1 else { return len }
var count = 0
permutations(string: self, pos: 0, len: len, count: &count)
return count
}
private func isValid(string: String, start: Int, end: Int) -> Bool {
let startIdx = string.index(string.startIndex, offsetBy: start)
let endIdx = string.index(string.startIndex, offsetBy: end)
let candidate = string[startIdx..<endIdx]
let num = Int(candidate)!
return num > 0 && num <= 26
}
private func permutations(string: String, pos: Int, len: Int, count: inout Int) {
if pos + 1 == len {
count = count + 1
return
} else if isValid(string: string, start: pos, end: pos + 1) {
permutations(string: string, pos: pos + 1, len: len, count: &count)
}
if pos + 2 == len && isValid(string: string, start: pos, end: pos + 2) {
count = count + 1
} else if isValid(string: string, start: pos, end: pos + 2) {
permutations(string: string, pos: pos + 2, len: len, count: &count)
}
}
}
"1234".permutations() // 3
A typical dp problem
private static int form(String s) {
int[] dp = new int[s.length() + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 1; i < s.length(); i++) {
int prev = s.charAt(i-1) - '0';
int val = s.charAt(i) - '0';
dp[i+1] = dp[i];
if (prev <= 2 && val <= 6) dp[i+1] += dp[i-1];
}
return dp[s.length()];
}
import java.util.*;
public class StringToLetts {
public static void main(String[] args) {
String input = "12342314517";
char[] charArr = input.toCharArray();
findCombs(charArr, 0, "");
}
public static void findCombs(char[] charArr, int fromI, String prefix) {
String newPrefix = prefix;
if(fromI == charArr.length -1){
System.out.println(prefix + charArr[fromI]);
} else if (fromI > charArr.length -1){
System.out.println(prefix + ",");
}
for(int i = fromI; i< charArr.length; i++){
char c = charArr[i];
if(c=='1' || c=='2'){
Integer integer = Integer.parseInt(c +"" + charArr[i+1] );
if(integer<=26){
if(i+2<charArr.length){
findCombs(charArr, i+2, newPrefix + "," + c + charArr[i+1]);
} else {
System.out.println(newPrefix + "," + c + charArr[i+1]);
}
}
}
newPrefix += "," + c ;
}
}
}
import java.util.*;
public class StringToLetts {
public static void main(String[] args) {
String input = "12342314517";
char[] charArr = input.toCharArray();
findCombs(charArr, 0, "");
input = "11111";
charArr = input.toCharArray();
findCombs(charArr, 0, "");
}
public static void findCombs(char[] charArr, int fromI, String prefix) {
String newPrefix = prefix;
if (fromI > charArr.length -1){
System.out.println(prefix );
}
for(int i = fromI; i< charArr.length; i++){
char c = charArr[i];
if((c=='1' || c=='2') && i+1 < charArr.length){
Integer integer = Integer.parseInt(c +"" + charArr[i+1] );
if(integer<=26){
if(i+2<charArr.length){
findCombs(charArr, i+2, newPrefix + "," + c + charArr[i+1]);
} else {
System.out.println(newPrefix + "," + c + charArr[i+1]);
}
}
}
newPrefix += "," + c ;
}
System.out.println(newPrefix);
}
}
private static int count(String s) {
int count = 0;
for (int i = 0; i < s.length()-1; i++) {
if(Byte.valueOf(s.substring(i,i+2))<=26){
count++;
}
}
return ++count; // add 1 because at least 1 solution exists if you break string into single digits
}
I think you code has few bugs for input "11111" count should be 5 but your code outputs 4. Also for if (i + i < c.length) it should be if (i + 1 < c.length).
Following is the corrected code
public static int numStrings(String s) {
if (s == null || s.length() == 0) {
return 0;
}
char[] c = s.toCharArray();
int charVal = -1;
int count = 0;
for (int i = 0; i < c.length; i++) {
if (i + 1 < c.length) {
String temp = Character.toString(s.charAt(i)) + s.charAt(i + 1);
charVal = Integer.parseInt(temp);
if (charVal >= 0 && charVal <= 26) {
System.out.println(temp);
count++;
}
}
}
return ++count;
}
Is a dynamic programig problem
public int GetNumberCombinations(string s)
{
// Skyp invalid chars, example: 00001 or 00000
int k = 0;
while (k < s.Length && !IsValid(s[k]))
k++;
if (k >= s.Length)
return 0;
int[] dp = new int[s.Length];
dp[k] = 1;
for (int i = k + 1; i < s.Length; i++)
{
dp[i] = dp[i - 1];
if (IsValid(s[i-1], s[i]))
dp[i]++;
}
return dp[s.Length - 1];
}
private bool IsValid(char c)
{
int n = (int)(c - '0');
return IsValid(n);
}
private bool IsValid(char c1, char c2)
{
if (c1 == '0')
return false;
int n1 = (int)(c1 - '0');
int n2 = (int)(c2 - '0');
int n = n1 * 10 + n2;
return IsValid(n);
}
private bool IsValid(int n)
{
return (n >= 1 && n <= 26);
}
Refactor from my previous post I don't need the array Time O(n) Space O(1)
public int GetNumberCombinations(string s)
{
// Skyp invalid chars, example: 00001 or 00000
int k = 0;
while (k < s.Length && !IsValid(s[k]))
k++;
if (k >= s.Length)
return 0;
int curr = 0;
int prev = 1;
for (int i = k + 1; i < s.Length; i++)
{
curr = prev;
if (IsValid(s[i-1], s[i]))
curr++;
prev = curr;
}
return curr;
}
private bool IsValid(char c)
{
int n = (int)(c - '0');
return IsValid(n);
}
private bool IsValid(char c1, char c2)
{
if (c1 == '0')
return false;
int n1 = (int)(c1 - '0');
int n2 = (int)(c2 - '0');
int n = n1 * 10 + n2;
return IsValid(n);
}
private bool IsValid(int n)
{
return (n >= 1 && n <= 26);
}
- Tanmay Shah May 17, 2016bool isValid(string s){ istringstream ibuf(s); int num; ibuf >> num; if(num>=1 && num <=26) return true; else return false; } int numEncoding(string s){ if(s.length()==0) return 1; if(s.length()==1) return 1; int num = 0; num += numEncoding(s.substr(1)); if(isValid(s.substr(0,2))) num += numEncoding(s.substr(2)); return num; }