Depth First Search Algorithm to Perform Phone Number Permutations

Given a string digits containing 2 to 9 inclusive, return in sorted lexicographic order all possible strings it could represent when mapping to letters on a phone dialpad.

These are the mappings on a phone dialpad:

| 2 | abc  |
| 3 | def  |
| 4 | ghi  |
| 5 | jkl  |
| 6 | mno  |
| 7 | pqrs |
| 8 | tuv  |
| 9 | wxyz |

Example 1
Input
digits = “23”
Output

1	["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Phone Number Permutation using Depth First Search Algorithm

We can try building the permutation digit by digit. We store the mapping in a dictionary, then look it up while during Depth First Search. We can spawn out the search tree digits by digits until we have built the size-n permutation where n is the length of the digits.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution:
    def phoneNumberPermutation(self, digits):
        m = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz"
        }
        ans = []
        def dfs(cur):
            if len(cur) == len(digits):
                ans.append(cur)
                return
            for n in m[digits[len(cur)]]:
                dfs(cur + n)
        dfs("")
        return ans

class Solution:
    def phoneNumberPermutation(self, digits):
        m = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz"
        }
        ans = []
        def dfs(cur):
            if len(cur) == len(digits):
                ans.append(cur)
                return
            for n in m[digits[len(cur)]]:
                dfs(cur + n)
        dfs("")
        return ans

The complexity is roughly O(3^N) if each digit has 3 possibilities. The space complexity is O(N) where N is the number of digits in the original string (and because we are using Recursion).

–EOF (The Ultimate Computing & Technology Blog) —