Saturday, September 13, 2014

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.

6 comments:

  1. English is an international language, no doubt about that. Native-speakers don’t have to worry about being misunderstood at the airport, but what to do if your native language is for example Human translation Chinese or Arabian, that is extremely challenging to discover. But they, betraying their folkways, learn English and visit foreign English speaking countries to find success in their future enterprise.

    ReplyDelete
  2. Is this a dynamic problem? Coz I can see a proper pattern in the series of sequences for each number.

    ReplyDelete
  3. Thank you so much for share such a wonderful post.I enjoyed a lot and i am very happy for getting the good article because rarely will get this type resources surely i will share this article for my friends because they will get the good tips and information.

    ReplyDelete
  4. This is something interesting. I think you intentionally made some wrong. I don't know why you did these? Feeling bad about that. Custom Essay Writing Services

    ReplyDelete
  5. I am very happy to read this. This is the kind of manual that needs to be given and not the random misinformation that’s at the other blogs. Appreciate your sharing this best posting. Custom Essay Writing Service

    ReplyDelete
  6. That's really a marvellous post. This post contains useful information which helps us a lot. I have never seen such a great post. Your wonderful post can inspire a lot and helps us. I visit your website often and share with my friend. college essay writing tips

    ReplyDelete