No. 55 - Translating Numbers to Strings

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.