Question: Given a
number, please translate it to a string, following the rules: 1 is translated
to 'a', 2 to 'b', …, 12 to 'l', …, 26 to 'z'. For example, the number 12258 can
be translated to "abbeh", "aveh", "abyh",
"lbeh" and "lyh", so there are 5 different ways to
translate 12258. How to write a function/method to count the different ways to
translate a number?
Analysis: Let's take
the number 12258 as an example to analyze the steps to translate from the
beginning character to the ending one. There are two possible first characters
in the translated string. One way is to split the number 12258 into 1 and 2258
two parts, and 1 is translated into 'a'. The other way is to split the number
12258 into 12 and 258 two parts, and 12 is translated into 'l'.
When the first one
or two digits are translated into the first character, we can continue to
translate the remaining digits. Obviously, we could write a recursive
function/method to translate.
Let's define a
function f(i)
as the count of different ways to translate a number starting from the ith digit, f(i)=g(i)*f(i+1)+h(i, i+1)*f(i+2).
The function g(i) gets 1 when the ith digit is in the range 1 to 9 which can be converted to a
character, otherwise it gets 0. The function h(i, i+1)
gets 1 the ith and (i+1)th digits are in the
range 10 to 26 which can also be converted to a character. A single digit 0
can't be converted to a character, and two digits starting with a 0, such as 01
and 02, can't be converted either.
Even though the
problem is analyzed with recursion, recursion is not the best approach because
of overlapping sub-problems. For example,
The problem to translate 12258 is split into two sub-problems: one is to
translate 1 and 2258, and the other is to translate 12 and 258. In the next
step during recursion, the problem to translate 2258 can also split into two
sub-problems: one is to translate 2 and 258, and the other is to translate 22
and 58. Notice the sub-problem to translate 258 reoccurs.
Recursion
solves problem in the top-down order. We could solve this problem in the
bottom-up order, in order to eliminate overlap sub-problems. That's to say, we start to translate the
number from the ending digits, and then move from right to left during
translation.
The following is the
C# code to solve this problem:
public static int
GetTranslationCount(int number)
{
if (number <= 0)
{
return 0;
}
string numberInString = number.ToString();
return GetTranslationCount(numberInString);
}
private static int
GetTranslationCount(string number)
{
int length = number.Length;
int[] counts = new int[length];
for (int i = length - 1; i >= 0; --i)
{
int count = 0;
if (number[i] >= '1' && number[i] <= '9')
{
if (i < length - 1)
{
count += counts[i + 1];
}
else
{
count += 1;
}
}
if (i < length - 1)
{
int digit1 = number[i] - '0';
int digit2 = number[i + 1] - '0';
int converted = digit1 * 10 + digit2;
if (converted >= 10 && converted
<= 26)
{
if (i <
length - 2)
{
count += counts[i + 2];
}
else
{
count += 1;
}
}
}
counts[i] = count;
}
return counts[0];
}
In order to simply
the code implementation, we first convert the number into a string, and then
translate.
The code with unit tests is shared at http://ideone.com/7wihgj.
More coding interview questions are discussed in my book< Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.
