Facebook Interview Question
Senior Software Development EngineersCountry: United States
Interview Type: Phone Interview
public int subStringReprensation(String inputNumber){
char[] inputChars=inputNumber.toCharArray();
int count=0;
if(inputChars.length==1){
return 1;
}
int i=0;
StringBuffer numberSampleString =new StringBuffer();
int numberSample=0;
while(i < inputChars.length){
numberSampleString.append(inputChars[i]);
numberSample=new Integer(numberSampleString.toString());
i++;
if(numberSample>26) break;
if(numberSampleString.length()==inputNumber.length()&& numberSampleString.length()==2 && numberSample<=26){
count++;
}else{
count+=subStringReprensation(inputNumber.substring(i,inputChars.length));
}
}
return count;
}
DP problem, just check the previous 1 and 2 numbers are valid or not;
int ValidDecoding(string s)
{
int t, l = s.length();
int * f = new int[l+1];
f[0] = 1;
for (int i = 1; i <= l; ++i)
{
f[i] = 0;
if (s[i-1] != '0')
f[i] += f[i-1];
if (i-2 >= 0){
t = 10 * (s[i-2] - '0') + s[i-1] - '0';
if (t > 9 && t < 27){
f[i] += f[i-2];
}
}
}
return f[l];
}
Dynamic programming version of my previous answer:
// We want to branch the string at every valid character and count the
// fully form string permutations indicated by when we reach a point where
// we can go no further, i.e. a full permutation has been calculated.
function branchAndCount(string, index, twoDigits, lookup) {
var sub;
// If we've fallen off the end of the string, and there was a string
// to begin with, we know that we have traversed a full permutation
// of one of the result strings and should count it in the final result;
if(index == string.length) {
return (string.length > 0 && !twoDigits) ? 1 : 0;
}
if(twoDigits) {
// We check the two-digit case including the digit from the previous iteration
// of the function. If this two digit number in the range 1 - 26 then we explore
// it further as it is a valid path.
sub = string.substring(index -1, index + 1);
// Dynamic programming version. The number of permutations rooted
// at this index has already been stored by the one-digit case.
// Look it up and reuse it.
return (sub >= '1' && sub <= '26') ?
lookup[index] : 0;
} else {
// The one-digit case is always valid, so we branch here in order to explore the
// succeeding one-digit and two-digit cases.
return (lookup[index] = branchAndCount(string, index + 1, false, lookup))
+ branchAndCount(string, index + 1, true, lookup);
}
}
// Wrapper function to invoke the main processing function correctly.
function countPermutations(string) {
var lookup;
lookup = [];
return branchAndCount(string, 0, false, lookup);
}
// Invoke
console.log(countPermutations('111'));
Here's my solution
Given a string x where x=[x0,x1....x[x.length]], the solution for x is the sum of all solutions of all substrings from i=1.. to x.length plus 1 if the length of string x is less than 27( a check).
Eg
solve(111) ---> check(111)+solve(11) + solve(1)
solve(11) ---> check(11) + solve(1)
solve(1) = 1 (base case)
Code:
static int solve(String x){
int sum = 0;
int i =1;
if (x.length()>0 && Integer.parseInt(x) < 27){
sum = 1;
}
while (i < x.length()){
sum = sum + solve(x.substring(i,x.length()));
i++;
}
return sum;
}
You can use a recursive function which remembers two things: the current index in the input string and the number we have got so far. From here, we can do two things: we can either add the current digit to the number we have so far or we can start a new number.
string s;
int solve(int idx, int sofar) {
if(sofar > 26) return 0;
// There can't be leading zeros
if(sofar == 0) return 0;
// This is a valid splitting of the string
if(idx == (int)s.size()) return 1;
int ret = solve(idx + 1, sofar * 10 + s[idx] - '0');
ret += solve(idx + 1, s[idx] - '0');
return ret;
}
The answer is solve(1, s[0] - '0')
Note that the states may repeat so you can use memoisation to reduce the time complexity to O(n)
I gave a solution which generates duplicates too and which were pruned later. But interviewer interested in solution without duplicates.
Like he said, you can just use memoization to avoid processing each case more than once:
int calc(int n, string& s, vector<int>& dp) {
if (n == s.size()) return 1;
if (dp[n] != -1) return dp[n];
int res = calc(n + 1, s, dp);
if (n+1 < s.size() && ) {
int next = s[n] + s[n+1] - '0' - '0';
if (next <= 26) res += calc(n + 2, s, dp);
}
return dp[n] = res;
}
The function calculates the number of mappings of the suffix of s starting at position n, so the original call must be calc(n, s, dp). dp has the same size as the string and is initialized with -1.
Solution in Java
import java.util.HashSet;
import java.util.Set;
public class GetNumValidMappings {
public static int getNumValidMappings(String input) {
try {
Integer.parseInt(input);
} catch (NumberFormatException e) {
return 0;
}
Set<String> validMappings = new HashSet<String>();
getAllValidMappings(validMappings, "", input);
return validMappings.size();
}
private static String convert(String input) {
char c;
try {
c = (char) (64 + Integer.parseInt(input));
if (c > 'Z') {
return null;
}
} catch (Exception e) {
return null;
}
return new String(new char[] {c});
}
public static void getAllValidMappings(Set<String> validMappings, String currentMapping, String remaining) {
if (remaining.length() == 0) {
validMappings.add(currentMapping);
} else if (remaining.length() == 1) {
String charMap = convert(remaining);
if (charMap != null) {
validMappings.add(currentMapping + charMap);
}
} else {
String singleCharMap = convert(remaining.substring(0, 1));
String doubleCharMap = convert(remaining.substring(0, 2));
if (singleCharMap != null) {
getAllValidMappings(validMappings, currentMapping + singleCharMap, remaining.substring(1));
}
if (doubleCharMap != null) {
getAllValidMappings(validMappings, currentMapping + doubleCharMap, remaining.substring(2));
}
}
}
public static void main(String[] args) {
String input = "12321";
System.out.println(getNumValidMappings(input));
}
/** Use dynamic programming technique.
* time: O(N)
* space: O(1)
*/
int mappingsCount(String str){
char[] arr = str.toCharArray();
int lastWays = 1;
int preLastWays = 1;
if( arr[arr.length-1] == '0' ){
preLastWays = 0;
}
for( int i = arr.length-2; i >= 0; i-- ){
int value = arr[i] - '0';
int curCount = 0;
if( value != 0 ){
curCount += preLastWays;
value = value*10 + arr[i+1]-'0';
if( value < 27 ){
curCount += lastWays;
}
}
lastWays = preLastWays;
preLastWays = curCount;
}
return preLastWays;
}
Using recursion to find count and strings
int arr[]={1,2,2,4};
int len;
//find combo of 2 strings at a time and then call recursively
//handle case of only one character
int findCombo(string str, int i)
{
int pos;
static int countCombo;
//cout<<"pos="<<pos<<endl;
//terminating condition
if(i>=len-2)
{
//look for combo of last 2 digits
if(arr[i]<=2 && arr[i+1]<7)
{
pos=arr[i]*10+arr[i+1];
cout<<str<<char(96+pos)<<endl;
++countCombo;
}
//print combo of individual characters
cout<<str<<char(96+arr[i])<<char(96+arr[i+1])<<endl;
return ++countCombo;
}
string newstr;
//if at leas 2 more digits found,create character from 2 digits and call further
if(i<len-2 && arr[i]<=2 && arr[i+1]<27)
{
pos=arr[i]*10+arr[i+1];
newstr=str+string(1,96+pos);
//cout<<"newstr"<<newstr<<endl;
findCombo(newstr,i+2);
}
//create character from 1 digit and call further
pos=arr[i];
newstr=str+string(1,96+pos);
//cout<<"newstr1"<<newstr<<endl;
findCombo(newstr,i+1);
return countCombo;
}
int main()
{
cout<<"Program to find combination of mapping numbers as string, returning the number of ways input string can be split into sub-strings"<<endl;
len=sizeof(arr)/sizeof(arr[0]);
cout<<"len="<<len<<endl;
string str;
int pos=0;
int count=findCombo(str,pos);
cout<<"count of combo="<<count<<endl;
/*string str1="kan";
string str2=str1+string(1,'h')+string(1,char(96+1));
cout<<"str2="<<str2<<char(96+1)<<endl;
*/return 0;
}
public class Example{
public static boolean validateInt(String ch) throws Exception
{
return Integer.parseInt(ch) <= 26;
}
public static int getSub(String remaining, int len) throws Exception
{
if (remaining.length() < len)
return 0;
if (remaining.length() == len && validateInt(remaining))
return 1;
if (remaining.length() == len && !validateInt(remaining))
return 0;
else
return getSub(remaining.substring(len), 1) + getSub(remaining.substring(len), 2);
}
public static int getlen(String num) throws Exception
{
return getSub(num, 1) + getSub(num, 2);
}
public static void main(String []args) throws Exception{
System.out.println(getlen("132"));
}
}
<?php
function combination($string, &$cache)
{
if (strlen($string) <= 1) {
return 1;
}
if (!isset($cache[$string])) {
$string1 = substr($string, 1);
$prefix = substr($string, 0, 2);
if ($prefix > 26) {
$cache[$string] = combination($string1, $cache);
} else {
$string2 = substr($string, 2);
$cache[$string] = combination($string1, $cache) + combination($string2, $cache);
}
}
return $cache[$string];
}
$cache = [];
var_dump(combination('1111235346345', $cache));
Forgot to handle '0'.
<?php
function combination($string, &$cache)
{
if (strlen($string) <= 1) {
if ($string == '0') {
return 0;
}
return 1;
}
if (!isset($cache[$string])) {
$prefix1 = $string[0];
$string1 = substr($string, 1);
if (combination($prefix1, $cache) == 0) {
$num1 = 0;
} else {
$num1 = combination($string1, $cache);
}
$prefix = substr($string, 0, 2);
if ($prefix > 26 || $prefix == '00') {
$cache[$string] = $num1;
} else {
$string2 = substr($string, 2);
$cache[$string] = $num1 + combination($string2, $cache);
}
}
return $cache[$string];
}
$cache = [];
var_dump(combination('12351200004034', $cache));
public int countDifferentWays(String str){
int n = str.length();
if(n < 2) return n;
int[] dp = new int[n];
dp[0] = 1;
dp[1] = (isOk(str,0,1)? 2: 1);
for(int i = 2; i <n; i++){
dp[i] = dp[i-1];
if(isOk(str,i-1,i)) dp[i]+=dp[i-2];
}
return dp[n-1];
}
private boolean isOk(String s, int from, int to){
return Integer.parseInt(s.substring(from, to+1)) < 27;
}
#include<stdio.h>
#include<conio.h>
#include<alloc.h>
int ar[20];
char ch[]={'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'};
void fun(int i,char a[20],int n)
{
if(i==n)
{
printf("%s\n",a);
}
else
{
char * temp=(char*)malloc(n);
sprintf(temp,"%s%c",a,ch[ar[i]-1]);
fun(i+1,temp,n);
free(temp);
if(i<n && (ar[i]*10+ar[i+1])<=26)
{
temp=(char *)malloc(n);
sprintf(temp,"%s%c",a,ch[ar[i]*10+ar[i+1]-1]);
fun(i+2,temp,n);
free(temp);
}
}
}
void main()
{
clrscr();
int info,tmp[20],t,i=0,j=0,n;
printf("Enter digit:");
scanf("%d",&info);
while(info!=0)
{
tmp[i]=info%10;
i++;
info=info/10;
}
n=i;
for(t=i-1;t>=0;t--)
{
ar[j]=tmp[t];
j++;
}
ar[j]=1000;
fun(0,"",n);
getch();
}
public class AlphabetMapping {
protected HashMap<String, String> am;
public AlphabetMapping() {
am = new HashMap<String, String>();
am.put("1", "A");
am.put("2", "B");
am.put("3", "C");
am.put("4", "D");
am.put("5", "E");
am.put("6", "F");
am.put("7", "G");
am.put("8", "H");
am.put("9", "I");
am.put("10", "J");
am.put("11", "K");
am.put("12", "L");
am.put("13", "M");
am.put("14", "N");
am.put("15", "O");
am.put("16", "P");
am.put("17", "Q");
am.put("18", "R");
am.put("19", "S");
am.put("20", "T");
am.put("21", "U");
am.put("22", "V");
am.put("23", "W");
am.put("24", "X");
am.put("25", "Y");
am.put("26", "Z");
}
public String number;
public ArrayList<String> calculateStrings(String number) {
if(number.length() == 1){
ArrayList<String> ret = new ArrayList<String>();
ret.add(this.am.get(number));
return ret;
}
else if (number.length() == 2) {
ArrayList<String> temp1 = calculateStrings(number.substring(0, 1));
ArrayList<String> ret = new ArrayList<String>();
String lastchar = number.substring(1);
for (String str : temp1){
ret.add(str.concat(this.am.get(lastchar)));
}
String last2 = this.am.get(number);
if(null != last2) {
ret.add(last2);
}
return ret;
}
else {
ArrayList<String> temp1 = calculateStrings(number.substring(0, number.length()-1));
ArrayList<String> ret = new ArrayList<String>();
String lastchar = this.am.get(number.substring(number.length()-1));
for (String str : temp1){
ret.add(str.concat(lastchar));
}
String last2char = this.am.get(number.substring(number.length()-2));
if(null != last2char) {
ArrayList<String> temp2 = calculateStrings(number.substring(0, number.length()-2));
for (String str : temp2){
ret.add(str.concat(last2char));
}
}
return ret;
}
}
/**
* @param args
*/
public static void main(String[] args) {
String str = "123";
AlphabetMapping am = new AlphabetMapping();
ArrayList<String> words = am.calculateStrings(str);
for(String word: words) {
System.out.println(word);
}
}
}
public class ValidMapping implements Runnable {
public ValidMapping() {};
static boolean DEBUG = false;
public void run()
{
DEBUG = true;
//test
for(String str : new String[] {"111", "11", "123"})
{
System.out.println("String :" + str + " Mappings: " + ValidMapping.Mapping(0, str.toCharArray()));
}
}
private static int Mapping(int i, char[] str)
{
if(i == str.length)
{
if(DEBUG)
{
System.out.println("\t" + new String(str));
}
return 1;
}
else
{
int sum = 0;
// one
if(str[i] >= '1' && str[i] <= '9')
{
sum += Mapping(i + 1, str);
}
//two
if(i+1 < str.length && ((str[i] == '1' && Character.isDigit(str[i+1]))
|| (str[i] == '2' && str[i+1] >= '1' && str[i+1] <= '6')))
{
sum += Mapping(i + 2, str);
}
return sum;
}
}
}
Here's my solution
Given a string x where x=[x0,x1....x[x.length]], the solution for x is the sum of all solutions of all substrings from i=1.. to x.length plus 1 if the length of string x is less than 27( a check).
Eg
solve(111) ---> check(111)+solve(11) + solve(1)
solve(11) ---> check(11) + solve(1)
solve(1) = 1 (base case)
Code:
static int solve(String x){
int sum = 0;
int i =1;
if (x.length()>;0 && Integer.parseInt(x) < 27){
sum = 1;
}
while (i < x.length()){
sum = sum + solve(x.substring(i,x.length()));
i++;
}
return sum;
}
My solution with dynamic programming:
public static int count(int n) {
if (n<=10) return 1;
if (n<=26) return 2;
String nstr = Integer.toString(n);
int first = Integer.parseInt(nstr.substring(0,1));
int second = Integer.parseInt(nstr.substring(1,2));
int head = Integer.parseInt(nstr.substring(1));
int tail = n>=100? Integer.parseInt(nstr.substring(2)) : 0;
if (first*10+second<=26) return count(head)+count(tail);
else return count(head);
}
this will work
public class AlphabetMap {
static int [][] dp;
static String pattern;
int count(int start, int end) {
if(start >= end || start < 0) return 0;
if(dp[start][end] != -1) return dp[start][end];
dp[start][end] =1;
for(int i=start;i<end;i++) {
// mixing i and i +1 in one num
int num = Integer.parseInt(pattern.substring(i,i+2));
if(num < 27) {
dp[start][end] += 1+ count(start,i-1) + count(i+2,end);
}
}
return dp[start][end];
}
public static void main(String [] args) {
AlphabetMap o = new AlphabetMap();
pattern = "1111";
dp = new int[pattern.length()][pattern.length()];
for(int i=0;i<dp.length;i++)
Arrays.fill(dp[i],-1);
int ans = o.count(0,pattern.length()-1);
System.out.println(ans);
}
}
package MANIPULAITON;
public class Count_Possible_Decodings_of_a_given_Digit_Sequence
{
public static void main(String []args)
{
String input = new String("111");
int length = input.length();
Count_Possible_Decodings_of_a_given_Digit_Sequence obj = new Count_Possible_Decodings_of_a_given_Digit_Sequence();
System.out.println(obj.countPossibleDecoding(input.toCharArray(),length));
}
private int countPossibleDecoding(char[] input, int length)
{
int count [] = new int[length+1];
count[0] = 1;
count[1] = 1;
for(int i =2;i<=length;i++)
{
count[i] = 0;
if(input[i-1] > '0')
{
count[i] = count[i-1];
}
if(input[i-2] <'2' || (input[i-2]=='2' && input[i-1] <'7'))
{
count [i] = count[i] + count[i-2];
}
}
return count[length];
}
}
private int getNumSubStrs(String str) {
int result = 0;
if (str == null || str.isEmpty()) {
return result;
} else {
for (int q = Integer.valueOf(str); q>0; q/=10) {
result++;
int d1 = q % 10;
int d2 = (q / 10) % 10;
if (d2 != 0 && stringMap.values().contains((d2*10 + d1))) {
result++;
}
}
}
return result;
}
}
//Time Complexity : O(n) [n= numbers.length()]
//Space Complexity : O(1)
public static int mappings(String numbers){
int last = 0;
int twolast = 0;
if(numbers.isEmpty()){
return 0;
}else{
twolast=1;//twolast = 1;
}
if(numbers.length()>2){
if(numbers.substring(0,2).compareTo("26")<=0){
last = 2;
}
}
for(int i=2;i<numbers.length();i++){
int one = last;
int two = 0;//0 ways to map the pair
if(numbers.substring(i-1,2).compareTo("26")<=0){//last two are an integer<=26.
two= twolast;//get ways to form the substring until two positions before
}else{
two= 0;
}
int current = one + two;
twolast = last;
last = current;
}
return last;
}
public static void main(String[] args){
String x="12786";
int r=solve(x);
System.out.println(r);
}
public static int solve(String x){
int sum = 0;
int i =1;
if (x.length()>0 && Integer.parseInt(x) < 27){
sum = 1;
}
while (i < x.length()){
sum = sum + solve(x.substring(i,x.length()));
i++;
}
return sum;
}
Isn't the answer just [ 1 + (# of valid two digit combinations < 26)! ]?
1, because you could count each number as one character. (E.x. 1111 would be AAAA)
Then you just have to loop over the string twice (once starting with the first letter, once starting with the second letter); count the number of two digit combinations < 26, take their factorial, and add them together.
For example:
11111111
would be 1 + 4! + 3! = 31. [ (11111111), or (11)(11)(11)(11), or 1(11)(11)(11)1 ]
This would run in O(n).
package com.core.javaTest;
import java.util.HashMap;
public class StringManipulationProblem {
private String inputString;
private String alphabetString;
private static HashMap<Integer, Character> map = new HashMap<Integer, Character>();
public StringManipulationProblem(String inputString){
this.inputString = inputString;
this.alphabetString = "";
}
static{
map.put(1, 'A');map.put(6, 'F');map.put(11, 'K');map.put(16, 'P');map.put(21, 'U');
map.put(2, 'B');map.put(7, 'G');map.put(12, 'L');map.put(17, 'Q');map.put(22, 'V');
map.put(3, 'C');map.put(8, 'H');map.put(13, 'M');map.put(18, 'R');map.put(23, 'W');
map.put(4, 'D');map.put(9, 'I');map.put(14, 'N');map.put(19, 'S');map.put(24, 'X');
map.put(5, 'E');map.put(10, 'J');map.put(15, 'O');map.put(20, 'T');map.put(25, 'Y');
map.put(26, 'Z');
}
public String getStringValue(int num){
String stringVal = "";
if(num <= 26){
stringVal = String.valueOf(map.get(num));
}
return stringVal;
}
public void solveProblem(){
char[] inputChar = this.inputString.toCharArray();
for(int i = 0 ; i < inputChar.length ; i++){
this.alphabetString = this.alphabetString + String.valueOf(map.get(Integer.parseInt(String.valueOf(inputChar[i]))));
}
System.out.println(this.alphabetString);
String outputString = "";
for(int j=0; j< this.inputString.length()-1; j++){
if(!getStringValue(Integer.parseInt(String.valueOf(inputChar[j])+String.valueOf(inputChar[j+1]))).isEmpty()){
outputString = this.alphabetString.substring(0, j) + getStringValue(Integer.parseInt(String.valueOf(inputChar[j])+String.valueOf(inputChar[j+1]))) + this.alphabetString.substring(j+2);
System.out.println(outputString);
}
}
}
public static void main(String str[]){
StringManipulationProblem smp = new StringManipulationProblem("19191");
smp.solveProblem();
}
int cno(string const &t) {
vector<int> d[2];
int n = t.size();
d[0].resize(n, 0);
d[1].resize(n, 0);
d[0][0] = 1;
d[0][1] = 1;
if(t.size() >= 2)
d[1][1] = ((t[0] - '0') * 10 + t[1] - '0') <= 26 ? 1 : 0;
for(int i = 2; i < n; i++) {
d[0][i] = d[1][i-1] + d[0][i-1];
if(((t[i - 1] - '0') * 10 + t[i] - '0') <= 26) {
d[1][i] = d[1][i-2] + d[0][i-2];
}
}
return d[0][n-1] + d[1][n-1];
}
//dynamic programming solution
O(N) time complexity and O(1) space complexity algorithm using dynamic programming
auto W = [](const string& S) {
const auto n = S.length();
int N[] = { 1, 0, 0 };
for (int i = 0; i < n; ++i) {
N[(i+1)%3] = '1' <= S[i] && S[i] <= '9' ? N[i%3] : 0;
if (i >= 1) {
N[(i+1)%3] += (S[i-1]-'0') * 10 + (S[i]-'0') <= 26 ? N[(i-1)%3] : 0;
}
};
return N[n%3];
};
public class HelloWorld{
public static void main(String []args){
System.out.println(method("1523"));
}
static int method(String input)
{
if(input.length()==0)
return 1;
int oneDigit=method(input.substring(1));
int twoDigit=0;
if(input.length()>1 && Integer.parseInt(input.substring(0,2))<=26)
twoDigit=method(input.substring(2));
return oneDigit+twoDigit;
}
}
public int numberOfCombination(String number)
{
if(number.length() == 1) {
return 1;
}
if(number.length() == 0) {
return 1;
}
int firstNumber = Integer.parseInt(number.substring(0, 2));
if(firstNumber < 26) {
//result = resul;
return numberOfCombination(number.substring(1)) + numberOfCombination(number.substring(2));
} else {
return numberOfCombination(number.substring(1));
}
}
public int numberOfCombination(String number)
{
if(number.length() == 1) {
return 1;
}
if(number.length() == 0) {
return 1;
}
int firstNumber = Integer.parseInt(number.substring(0, 2));
if(firstNumber < 26) {
//result = resul;
return numberOfCombination(number.substring(1)) + numberOfCombination(number.substring(2));
} else {
return numberOfCombination(number.substring(1));
}
}
static public int numberOfCombination(String number)
{
if(number.length() == 1) {
return 1;
}
if(number.length() == 0) {
return 1;
}
int firstNumber = Integer.parseInt(number.substring(0, 2));
if(firstNumber < 26) {
//result = resul;
return numberOfCombination(number.substring(1)) + numberOfCombination(number.substring(2));
} else {
return numberOfCombination(number.substring(1));
}
}
static int many = 0;
static void findPossibleCombination(String num, int start) {
if (start == num.length()) {
many++;
return;
}
for (int size = 0; size < 2; size++) {
if (start + size == num.length()) {
return;
}
final String first = num.substring(start, start + size + 1);
final int value = Integer.valueOf(first);
if (0 <= value && value < 25) {
findPossibleCombination(num, start + size + 1);
}
}
}
Regular recursive approach
static void allPossibleMappings(String str) {
Map<Integer, Character> map = new HashMap<>();
for(int i=0; i<26; i++) {
map.put(i+1, (char)('A'+i));
}
mappings(map, str, 0, "");
}
static void mappings(Map<Integer, Character> map, String str, int start, String res) {
if(start == str.length()) {
System.out.println(res);
return;
}
for(int i=1; i + start <= str.length(); i++) {
if(map.containsKey(Integer.parseInt(str.substring(start, start+i)))) {
mappings(map, str, start+i, new String(res+map.get(Integer.parseInt(str.substring(start, start+i)))));
}
else {
return;
}
}
}
Non-recursive version. C++
Idea is that on every digit you can
1. Treat it as a standalone digit
2. Complete 2-digit combo started on previous digit
3. Start new 2-digit combo
cases 1 and 2 add up to complete_mappings
case 3 carries previous value of complete_mappings over to next iteration as incomplete_mappings
bool CanComplete(string str, int i)
{
if ( i == 0)
return false;
if ( str[i-1] == '0') return false;
if ( str[i-1] == '1') return true;
if ( str[i-1] == '2' && str[i] < '7') return true;
return false;
}
int MappingsNum(string str)
{
int complete_mappings_num = 1;
int incomplete_mappings_num = 0;
int length = str.size();
for ( int i = 0; i < length; ++i)
{
if ( str[i] < '0' || str[i] > '9') // non-valid characters, mapping is impossible
return 0;
int next_complete_mappings_num = complete_mappings_num; // simple one digit mapping
if (CanComplete(str, i))
next_complete_mappings_num += incomplete_mappings_num; // add 2 digit mapping completed on this digit
incomplete_mappings_num = complete_mappings_num; // in case we can start new 2digit mapping
complete_mappings_num = next_complete_mappings_num; // end processing this digit
}
return complete_mappings_num;
}
#include <stdio.h>
int main(int argc, char *argv[])
{
char num[] = "111";
int count=1, i, sum;
int first_value, second_value;
for(i=0; num[i+1] != '\0'; i++)
{
first_value = (num[i] - '0') * 10 ;
second_value = num[i+1] - '0' ;
if( (first_value + second_value) <= 26)
count++;
}
printf("count:%d\n", count);
}
int count;
int get_number(char *str, int start, int end)
{
int num = 0;
while( start <= end)
{
num = num * 10 + str[start] - '0' ;
start++;
}
return num;
}
int mapping(char *str, int start, int len)
{
int i, num;
if( start == len)
{
count++;
return;
}
for(i = start; (i < len) && (i < (start + 2) ); i++)
{
num = get_number(str, start , i);
if( num <= 26)
mapping(str, i + 1, len);
}
return count;
}
Dynamic programming is the key here. However, they mention it should work with *any* number sequence. Consider cases like "0000001" or "405006".
import string
def int2str( n ):
return string.ascii_lowercase[n]
def getNumCombinations( stringNumber ):
if len(stringNumber) == 1:
if int(stringNumber) > 0:
return 1
else:
return 0
elif len(stringNumber) == 2:
currInt = int(stringNumber)
if currInt >=1 and currInt < 10:
return 1
else:
return 2
n1 = int(stringNumber[0])
n2 = int(stringNumber[:2])
if n1 == 0:
if n2 != 0:
return getNumCombinations( stringNumber[1:])
elif n2 == 0:
return getNumCombinations( stringNumber[2:])
else:
if n2>0 and n2<=26:
return getNumCombinations( stringNumber[1:])+getNumCombinations( stringNumber[2:])
else:
return getNumCombinations( stringNumber[1:])
Looks like a simple Dynamic Programming problem. Start with a string of length 1. Initialize answer with 1 since 1 character can be a valid string. Add a new character to the string. If that character and the previous character together makes a valid string number (e.g. "23" but NOT "32") then add f(i-2) to the answer since this new 2-digit number permutes with those i-2 digits to create new valid combinations.
No need to memoize in 1-d array since only two valid states are required.
bool isValidStringNumber(char*str, int st, int end)
{
if(end-st>2)
return false;
if((str[st]>'2' || str[st+1]>'6') && end-st==2)
return false;
return true;
}
int StringNumberSplit(char*str, int st, int end) // mapping 1->a, 2->b , ... 26->z
{
int prev = 1;
int prevprev = 1;
int ans = 1;
for(int i=1;i<end;i++)
{
ans = prev ;
if(isValidStringNumber(str,i-1, i+1))
{
ans = ans + prevprev;
}
prevprev = prev ;
prev = ans ;
}
return ans;
}
public class Count_Possible_Decodings_of_a_given_Digit_Sequence
{
public static void main(String []args)
{
String input = new String("121");
int length = input.length();
Count_Possible_Decodings_of_a_given_Digit_Sequence obj = new Count_Possible_Decodings_of_a_given_Digit_Sequence();
System.out.println(obj.countPossibleDecoding(input.toCharArray(),length));
}
private int countPossibleDecoding(char[] input, int length)
{
int count [] = new int[length+1];
count[0] = 1;
count[1] = 1;
for(int i =2;i<=length;i++)
{
count[i] = 0;
if(input[i-1] > '0')
{
count[i] = count[i-1];
}
if(input[i-2] <'2' || (input[i-2]=='2' && input[i-1] <'7'))
{
count [i] = count[i] + count[i-2];
}
}
return count[length];
}
}
this is pretty easy if you think in terms of Dp approach.
Lets say we have String as "1" so our output will be 1 because we only form 'A'
but if we add 2 to the existing string "12" then output is "AB" and "L" so if you see
the logic is when you add a character to an existing string the number of combinations increase by combining last 2 digits
in dp it can be formulized As
d[i]=dp[i-1]+dp[i-2](if the last 2 digits combined is smaller than 27)
else dp[i]=dp[i-1];
code is as below
- blackfever August 17, 2014