## 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.

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.

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

2. Great Article Cloud Computing Projects

Networking Projects

Final Year Projects for CSE

JavaScript Training in Chennai

JavaScript Training in Chennai

The Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training

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

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

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.

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

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

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

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.

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

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,

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,

11. It’s great because of the knowledge you share with us, I will always follow your blog and will share your blog with my friends
- Lenny Face

12. I thought this would be a recursion solution but I can't see the recursion. How are you calling this recursively?

13. Excellent article I like this kind of articles in which you can get tons of knowledge with few examples, keep writing like this and many people opt for your content.

DedicatedHosting4u.com

14. great post keep doingchange-color-of-text-in-html

15. خدمة كتابة السيرة الذاتية الإحترافية says
Where to find best jobs in the world why not visit our website for jobs in saudi arabia other than saudi arabia you can look for jobs in pakistan and where you feel your cv is not professional feel free to use our Professional resume writing services we are here to help you out there in a world where completion is moving fast

16. This post your blog is very useful to me. Select Best IAS Coaching Institutes in Navi Mumbai.
Best IAS Coaching Institutes in Navi Mumbai
Top IAS coaching in navi Mumbai

17. Thank you for sharing useful information with us. please keep sharing like this.
And if anyone like to take admission in Dehardun then check this.

Tula's Institute Best BCA College in Dehradun

18. This article is a great article that I have seen so far in my blog career, it helps me a lot to develop the logic of strings translating numbers in Python, and will continue to do so in the future.

hire python developers in US

19. Interesting stuff to read. Keep it up.
Please Visit Us to know more about Best IAS Coaching in Bangalore

20. Great article.Keep it up! metal stamping company