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.

12 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
    Replies
    1. Hi Harry,

      Thanks for highlighting this and indicating about No. 55 - Translating Numbers to Strings where more study and thought is necessary.

      If I buy a Route 53 domain name, can I create an email address and use it with gmail? If so, how?
      I do not want to use Workmail, or SES or an EC2 instance.
      All I want is a username, password, and SMTP and whatever else is needed to link my route 53 email to gmail.

      The AWS Serverless Application Model (AWS SAM) extends AWS CloudFormation to provide a simplified way of defining the Amazon API Gateway APIs, AWS Training USA AWS Lambda functions, and Amazon DynamoDB tables needed by your serverless application

      Very useful article, if I run into challenges along the way, I will share them here.

      Cheers,
      Kevin

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

    ReplyDelete
    Replies
    1. Hello Harry,

      Grazie! Grazie! Grazie! Your blog is indeed quite interesting around No. 55 - Translating Numbers to Strings! I agree with you on lot of points!

      There wouldn't be any static charges such as monthly fee for setting up a static website beyond the resources that you are expecting to use. The Simple Monthly Calculator in this case would be dependent on the expected Data Transfer, S3 usage and Route 53 config usage.

      The API tools can be both used for spin up services and the written scripts AWS Training USA . These scripts could be coded in Perl, bash or other languages of preference.

      Follow my new blog if you interested in just tag along me in any social media platforms!

      Thank you,
      Kevin

      Delete
  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
  7. This is a useful article for both novice programmers and experienced programmers. You are an excellent blogger, in our company buyanessay.co lacks a technical specialist, we are interested in such an author as you.

    ReplyDelete
  8. Hello Harry,


    Interesting piece! Great to see someone write Translating Numbers to Strings
    who is not a fanatic or a complete skeptic.

    But now it was not letting me use the forum without putting a new nickname and new email address. Every time I was putting my original nickname udasxilinx it was saying nickname is already used. But this does not make sense, because the nickname is used by me and I am using same email to login. Also it is not letting me use my actual email id when I used in as forum email. So I am forced to use a different nickname (udayxilinx) and different email address (uday.das@gmail.com) though from the root I am using the same old company's email id.

    By the way do you have any YouTube videos, would love to watch it. I would like to connect you on LinkedIn, great to have experts like you in my connection (In case, if you don’t have any issues).


    Regards,
    Abhiram

    ReplyDelete
  9. Merhaba,


    Great post. Well though out. This piece reminds me when I was starting out No. 55 - Translating Numbers to Strings after graduating from college. AWS Training


    This is Erin from Amazon Web Services. I took a look at the support case you provided, I see that one of our agents was able to assist and resolve the case.

    Please let us know if there is anything else we can help with!


    Awesome! Thanks for putting this all in one place. Very useful!

    Kind Regards,
    Radhey

    ReplyDelete
  10. Howdy Mate,


    This is indeed great! But I think perhaps you are generally referring Translating Numbers to Strings.which is getting unsustainable


    I have a problem with cost allocation tags. AWS Training I added a number of custom tags to my AWS resources. Activated the tags using activation GUI. I can see the tag keys as dimensions for Cost Explorer filters but no tag values are shown for filtering (only record "No TagKey"). More than a week passed since I added and activated the tags but nothing changes. Please advise.

    Once again thanks for your tutorial.

    Merci Beaucoup,
    Radhey

    ReplyDelete