CareerCup

recursive...

function(str) {

If str.length < 1 return 0;

x=0; //number of ways IF we can map first two digits

//if first two characters have a valid mapping, then count the ways into 'x'
If str.length >= 2 and str[1 .. 2] is in range(1,26) {  
    x = 1 + function(str[2 ... n]);
}

//max of interpreting first 2 digits as valid map OR first digit as valid
return max( x, 1+function(str[1 ... n] );  

}

Because of overlapping subproblems, memoize to make it DP (top down DP).

If you are NOT that nervous in interview, do it bottom up using a table.

Clarification:

For eg; if the mapping is given as

1: a
0 : a
10:aa

We get aa from 10, but we can do it either 1->a, 0->a or 10->aa. Do we count this as two or one? (i.e. do you count based on the splits, or based on the unique resulting string?)

Assuming you are looking for different split points, rather than resulting string

A dynamic programming algorithm can be written to use the following recursion:

Count[m+1] = Sum_{j=0 to m} IsMapped(j, m+1)*Count[j]

Where IsMapped returns 0 or 1 depending on whether substring from position j to m+1 can be mapped or not (not including j, but including m+1).

Quadratic time, linear space.

If the resulting strings need to be unique, this becomes more complicated.

Btw, this is the recursive approach I used:

count(str):
if empty(str):
return 1
result := 0
if valid_map(str[-1]):
result := result + count(str[:-1])
if str.length > 1 and valid_map(str[-2]):
result := result + count(str[:-2])
return result

Based on this recursive formula, DP can be easily implemented by storing the last two previous solutions for n - 1 and n - 2 (like Fibonacci sequence) so that memory is constant and running time is linear.

#include <cstdio>
#include <iostream>
#include <map>
#include <vector>
#define DEBUG
//#undef  DEBUG

using namespace std;

map<int, char> dic;

bool judgeValid(string code)
{
	if(code.size() > 1 && code[0] == '0')
	{
		return false;
	}

	int num = atoi(code.c_str());

	if(dic.find(num) != dic.end())
	{
		return true;
	}
	return false;
}

char getValue(string code)
{
	int num = atoi(code.c_str());
	return dic[num];
}

void printCode(int cur, vector<char> dcode, string source)
{
	if(cur == source.size())
	{
		for(vector<char>::iterator it = dcode.begin(); it != dcode.end(); ++it)
		{
			cout << (*it);
		}
		cout << endl;

		return;
	}
	
	string tmp;
	for(int i = cur; i < source.size(); ++i)
	{
		tmp.push_back(source[i]);
		if(judgeValid(tmp))
		{
			dcode.push_back(getValue(tmp));
			printCode(i + 1, dcode, source);
			dcode.pop_back();
		}
	}
}

#ifdef DEBUG

#endif

#ifdef DEBUG
void testMap()
{
	for(map<int, char>::iterator it = dic.begin(); it != dic.end(); ++it)
	{
		cout << it->first << ", " << it->second << endl;
	}
}

void testJudgeValid()
{
	bool tmp;
	vector<string> tvec;
	tvec.push_back(string("10"));
	tvec.push_back(string("16"));
	tvec.push_back(string("30"));
	tvec.push_back(string("01"));
	tvec.push_back(string("00"));
	tvec.push_back(string("8"));

	for(vector<string>::iterator it = tvec.begin(); it != tvec.end(); ++it)
	{
		tmp = judgeValid(*it);
		cout << (tmp ? "True" : "False") << endl;
	}
}

void testPrintCode()
{
	vector<string> tvec;
	tvec.push_back("12632");
	tvec.push_back("111");
	tvec.push_back("101");
	for(vector<string>::iterator it = tvec.begin(); it != tvec.end(); ++it)
	{
		cout << "Test " << (*it).c_str() << ":" << endl;
		printCode(0, vector<char>(), *it);
		cout << endl;
	}
}
#endif

int main()
{
	int i = 0;
	for(i = 1; i <= 26; ++i)
	{
		dic[i] = char('a' + i - 1);
	}

#ifdef DEBUG
	testMap();
	testJudgeValid();
	testPrintCode();
#endif
	return 0;
}

private int count=0;

	public Calculate() {
		noOfWays("" ,"1263256732");
		System.out.println(count);

	}

	private void noOfWays(String B ,String A){
		if(A.length()==0){
			count++;
			System.out.println(B);
			return;
		}
		if(A.length()>1){
			char c1 = A.charAt(0);
			char c2 = A.charAt(1);

			int a1 = c1 -'0';
			int a2 = c2 - '0';

			if(a1!=0){
				char b = (char)('a'+a1-1);
				noOfWays(B + b, A.substring(1));
			}

			if(a1>0 && a1<3 && a2<=6){
				char b = (char)('a' + (a1*10 + a2)-1);
				noOfWays(B + b, A.substring(2));
			}
		}else{
			char c1 = A.charAt(0);
			int a1 = c1 -'0';
			noOfWays(B + (char)('a'+a1-1), A.substring(1));
		}
	}

private void DifferentMapping(string input, string current, int index)
        {
            if (index == input.Length)
            {
                Console.WriteLine(current);
                //index--;
            }
            else
            {
                string intToMap = "";
                
                    intToMap = input[index].ToString();
                    
                    DifferentMapping(input, current + Map(intToMap), index+1);
                    intToMap = intToMap + input[index];
                    if (Convert.ToInt32(intToMap) <= 26 && index < input.Length-1)
                    {
                        
                        DifferentMapping(input, current + Map(intToMap), index+2);
                    }
                    
                
            }
        }
        private char Map(string intToMap){
            return (char)(Convert.ToInt32(intToMap) + ((int)'a'));
        }

What about this DP solution
Let S contains the given number

F(n) = F(n-1) + F(n-2), if S[n-1,n] <= 26
           F(n-1),                 if   S[n-1,n] > 26
F(1) = 1
F(2) = 2, if S[1,2] <= 26 else 1