Which Letters Equal Which Numbers On Phone

Howdy fellow devs 👋! Today nosotros are going to discuss a popular problem which is asked past many tech giants in coding interviews.

Letter Combinations Of A Phone Number

Problem Statement

Given a string containing digits from 2-9 inclusive, return all possible letter of the alphabet combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any messages.

LeetCode 17 Keypad

Constraints:

0 ≤ digits.length ≤ iv
digits[i] is a digit in the range ['2', '9'].

Examples

Example one:

            Input: digits = "23" Output: ["advertisement","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

            Input: digits = "" Output: []

Case three:

            Input: digits = "two" Output: ["a","b","c"]

Analysis

Nosotros all accept seen above paradigm in the adept olden days 💗 where we used to take better music and improve life 😃. Earlier the time of affect screen, mobile phones used to accept this keypad where each button represented some symbols — numbers, letters, etc.

In this question besides, we need to observe all the combinations of letters which can be obtained if a number is pressed. For eastward.g., from the in a higher place image 3 represents def and 5 represents jkl and so if someone were to printing 35, they will go one of the following combinations —

            dj, dk, dl, ej, ek, el, fj, fk, fl

We need to find these combinations. If we expect at it more closely, at that place are a few things to notice —

We need to accept care of only numbers 2,3,four,5,6,seven,8,ix.
At that place can be a maximum of 4 characters in a given string.
The effect needs to be the Cartesian product of the given letters' combination.

Approach

How do we solve it? If you are thinking well-nigh recursion , then you are on the correct track. At each stage of recursion there will be a digit that will represent some characters, and and then nosotros will recursively transport the next digit to await for those set of characters that could be appended in our outcome cord.

We tin follow beneath steps —

Construct an array where each index represents the respective letters on the keypad corresponding to that number. Since there are no letters with respect to 0 and 1, for the sake of ease of accessibility, we will put dummy values on those indices. Such an array will look something similar this —

            lettersAndNumbersMappings = [         "Anirudh",         "is awesome",         "abc",         "def",         "ghi",         "jkl",         "mno",         "pqrs",         "tuv",         "wxyz"     ]

Write a helper role which will contain the crux of our logic. This part will be called recursively.
In the recursive function, nosotros should take a terminating condition. In our case, think when our recursion volition stop 🤔? Information technology will terminate when nosotros have scanned all the characters in the given string. At that point, we will return.
If the terminating condition is not met then nosotros will first find the messages corresponding to the current characters in the given string past referring to our mappings array.
We will and so loop for all the characters in the string obtained in the previous footstep and call make recursive calls with the strings after appending the current grapheme and the cord in the previous footstep.

Fourth dimension Complexity

The numbers in input string tin can represent strings of length of 3 or 4. Let m be the number of digits that map to iii letters and n be the number of digits that map to iv messages. Thus, the overall fourth dimension complexity will be O(3^yard × 4ⁿ) .

Space Complexity

The recursive call will use the stack memory equal to O(3^{one thousand} × ivⁿ) and this will exist the infinite complication.

Code

Java

                          public              grade              LetterCombinationsOfAPhoneNumber              {              private              static              List                              <                String                >                            letterCombinations              (              String              digits)              {              // Resultant list              List                              <                String                >                            combinations              =              new              ArrayList                              <                >                            (              )              ;              // Base condition              if              (digits              ==              zippo              ||              digits.              isEmpty              (              )              )              {              return              combinations;              }              // Mappings of messages and numbers              String              [              ]              lettersAndNumbersMappings              =              new              Cord              [              ]              {              "Anirudh"              ,              "is awesome"              ,              "abc"              ,              "def"              ,              "ghi"              ,              "jkl"              ,              "mno"              ,              "pqrs"              ,              "tuv"              ,              "wxyz"              }              ;              findCombinations              (combinations,              digits,              new              StringBuilder              (              )              ,              0              ,              lettersAndNumbersMappings)              ;              return              combinations;              }              private              static              void              findCombinations              (              List                              <                String                >                            combinations,              String              digits,              StringBuilder              previous,              int              index,              String              [              ]              lettersAndNumbersMappings)              {              // Base of operations status for recursion to finish              if              (index              ==              digits.              length              (              )              )              {              combinations.              add together              (previous.              toString              (              )              )              ;              return              ;              }              // Get the messages corresponding to the current alphabetize of digits cord              String              letters              =              lettersAndNumbersMappings[digits.              charAt              (index)              -              '0'              ]              ;              // Loop through all the characters in the current combination of letters              for              (              char              c              :              letters.              toCharArray              (              )              )              {              findCombinations              (combinations,              digits,              previous.              append              (c)              ,              index              +              one              ,              lettersAndNumbersMappings)              ;              previous.              deleteCharAt              (previous.              length              (              )              -              1              )              ;              }              }              }

Python

                          def              findCombinations              (combinations,              digits,              previous,              index,              lettersAndNumbersMapping)              :              # Base condition to terminate recursion              if              alphabetize              ==              len              (digits)              :              combinations.suspend(previous)              return              # Get the messages corresponding to the current index of digits string              messages              =              lettersAndNumbersMapping[              int              (digits[alphabetize]              )              ]              # Loop through all the characters in the current combination of letters              for              i              in              range              (              0              ,              len              (letters)              )              :              findCombinations(combinations,              digits,              previous              +              letters[i]              ,              index              +              1              ,              lettersAndNumbersMapping)              def              letterCombinations              (digits:              str              )              -              >              List[              str              ]              :              # Resultant listing              combinations              =              [              ]              # Base condition              if              digits              is              None              or              len              (digits)              ==              0              :              render              combinations              # Mappings of messages and numbers              lettersAndNumbersMapping              =              [              "Anirudh"              ,              "is awesome"              ,              "abc"              ,              "def"              ,              "ghi"              ,              "jkl"              ,              "mno"              ,              "pqrs"              ,              "tuv"              ,              "wxyz"              ]              findCombinations(combinations,              digits,              ""              ,              0              ,              lettersAndNumbersMapping)              return              combinations

JavaScript

                          var              letterCombinations              =              function              (              digits              )              {              // Resultant list              permit              combinations              =              [              ]              ;              // Base condition              if              (digits              ==              null              ||              digits.length              ==              0              )              {              return              combinations;              }              // Mappings of messages and numbers              const              lettersAndNumbersMappings              =              [              "Anirudh"              ,              "is awesome"              ,              "abc"              ,              "def"              ,              "ghi"              ,              "jkl"              ,              "mno"              ,              "pqrs"              ,              "tuv"              ,              "wxyz"              ]              ;              findCombinations              (combinations,              digits,              ""              ,              0              ,              lettersAndNumbersMappings)              ;              return              combinations;              }              ;              function              findCombinations              (              combinations,                digits,                previous,                index,                lettersAndNumbersMappings              )              {              // Base condition for recursion to stop              if              (index              ==              digits.length)              {              combinations.              button              (previous)              ;              return              ;              }              // Get the letters corresponding to the electric current index of digits string              let              letters              =              lettersAndNumbersMappings[digits[index]              -              '0'              ]              ;              // Loop through all the characters in the current combination of letters              for              (              let              i              =              0              ;              i              <              messages.length;              i++              )              {              findCombinations              (combinations,              digits,              previous              +              letters[i]              ,              index              +              i              ,              lettersAndNumbersMappings)              ;              }              }              ;

Kotlin

            fun              letterCombinations              (digits:              String              )              :              Listing                              <                String                >                            {              // Resultant list              val combinations:              MutableList                              <                Cord                >                            =              mutableListOf              (              )              // Base of operations status              if              (digits.              isEmpty              (              )              )              {              return              combinations              }              // Mappings of letters and numbers              val lettersAndNumbersMappings              =              arrayOf              (              "Anirudh"              ,              "is awesome"              ,              "abc"              ,              "def"              ,              "ghi"              ,              "jkl"              ,              "mno"              ,              "pqrs"              ,              "tuv"              ,              "wxyz"              )              findCombinations              (combinations,              digits,              StringBuilder              (              )              ,              0              ,              lettersAndNumbersMappings)              return              combinations              }              fun              findCombinations              (combinations:              MutableList                              <                String                >                            ,              digits:              String              ,              previous:              StringBuilder              ,              index:              Int              ,              lettersAndNumbersMappings:              Assortment                              <                String                >                            )              {              // Base condition for recursion to terminate              // Base of operations condition for recursion to terminate              if              (alphabetize              ==              digits.length)              {              combinations.              add together              (previous.              toString              (              )              )              return              }              // Get the letters corresponding to the electric current index of digits string              // Get the letters corresponding to the current index of digits cord              val letters              =              lettersAndNumbersMappings[digits[index]              -              '0'              ]              // Loop through all the characters in the current combination of letters              // Loop through all the characters in the current combination of messages              for              (c in letters.              toCharArray              (              )              )              {              findCombinations              (combinations,              digits,              previous.              suspend              (c)              ,              index              +              one              ,              lettersAndNumbersMappings)              previous.              deleteCharAt              (previous.length              -              1              )              }              }

Complete Code

Java
Python
JavaScript
Kotlin

Conclusion

Congratulations 👏! We have solved one more trouble from LeetCode.

I promise you enjoyed this post. Feel gratuitous to share your thoughts on this.

You can find the complete source code on my GitHub repository. If yous similar what yous acquire, feel free to fork 🔪 and star ⭐ it.

Till next time… Happy coding 😄 and Namaste 🙏!