Leetcode:273 Integer to English Words

Question:

Convert a non-negative integer num to its English words representation.

Example 1:

Example 2:

Example 3:

Example 4:

You may have noticed I have highlighted a few keywords in the examples. Try to look for some sort of pattern before you proceed.

Intuition

I must need some sort of mapping for unique identifiers like :

Realization 1 : At a high level we can figure out the scale of number i.e thousand, million and billion easily.

Realization 2 : In the examples, you will notice a repeating pattern. If we have a function that converts numbers upto a 100 to words for us, we can reuse the logic for subsequent combinations.

Solution :

Runtime : 32 ms , Space : 14.2 MB

Time Complexity : O(N)

We use concatenate ‘+’ here which means everytime the entire length of the string is iterated over. We can further optimize this by using “”.join() instead of string concatenation.

Space Complexity : O(1)

Optimized Solution :

Runtime : 24 ms, Space : 14.2 MB

I am a software developer working at Oracle.