Letter Combinations of a Phone Number (Leetcode 17)

Difficulty: Medium Link: Leetcode 17

The Swift Nerd

Problem description

Given a string containing digits from 2-9 inclusive, return all possible letter 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 letters.

Examples

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Input: digits = ""
Output: []
Input: digits = "2"
Output: ["a","b","c"]

Constraints

  • 0 <= digits.length <= 4
  • digits[i] is a digit in the range ['2', '9']

Solution

Let’s take an example for input “23”. “2” will correspond to letters [“a”, “b”, “c”] and “3” to [“d”, “e”, “f”]. Now every alphabet needs to form a combination with every letter in the other digits. So “a” will need to couple with “d”, then “e” and finally “f”. We need to repeat the same for “b” and so on. We can observe that this is a brute force DFS and we need to stop once we exceed the bounds of the input.

In the above example, every letter will combine with letters in the other digits to give these combinations:

a with (d,e,f) = ["ad", "ae", "af"]
b with (d,e,f) = ["bd", "be", "bf"]
c with (d,e,f) = ["cd", "ce", "cf"]
Total result = combinations(a) + combinations(b) + combinations(c)
= ["ad", "ae", "af","bd", "be", "bf", "cd", "ce", "cf"]

Approach

We can use the backtracking pattern to build our solution. For every recursiveCall, we can list out our eligible candidates for the subproblem, and iterate over our candidates and use them to build a partial solution and passing it to the recursive call. In this case, we are passing a string variable and after iterating over all the current digits, we will append current letter in the string and pass to next recursive call. Since this recursion will go on forever, we need to keep an index parameter to keep track of our location. Whenever our index exceeds the input bounds, this means that we have processed one branch of the possible combinations and we need to add it to the result.

func combinations_dfs_helper(_ digits:String,_ current:String,_ index:Int,_ output: inout [String]){
//Exit condition
if index == digits.count {
output.append(current)
return
}
// logic for exploring candidates
}

One tricky thing in swift is that Strings are not randomly accessible. So either we need to convert the string into a char array or use String.Index API to get a String at a certain index. We have used String.Index here but feel fee to explore other options. We pass the String.StartIndex and offset it by the current Index value which gives you the String value at an index.

Exit condition and inout parameter

For collecting out result, we can define a String Array and pass it as an “inout” parameter to the recursive calls. Before returning from the exit condition, we make sure to add the current element to the result array. We need to check for empty input as well, otherwise “” will be appended to our result array.

func letterCombinations(_ digits: String) -> [String] {
// Empty check
guard digits.isEmpty == false else { return [] }
// Result array
var output = [String]()
// recursive call with "" and index : 0
combinations_dfs_helper(digits,"",0,&output)
return output
}

Combinations mapping

The last thing left is to have a map to store the digit:alphabets combinations. We can simply use a swift dictionary of [Character:String] mapping to store in a class property. We can also use an array to map digits to the index in the collection but make sure to add sentinel values for first two indexes ;).

Final Solution

class Solution {
let map:[Character:String] = ["2" : "abc", "3": "def", "4" : "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv","9":"wxyz"]
func letterCombinations(_ digits: String) -> [String] {
guard digits.isEmpty == false else { return [] }
var output = [String]()
combinations_dfs_helper(digits,"",0,&output)
return output
}
func combinations_dfs_helper(_ digits:String,_ current:String,_ index:Int,_ output: inout [String]){
if index == digits.count {
output.append(current)
return
}
let charIndex = digits.index(digits.startIndex, offsetBy:index)
let currentChar = digits[charIndex]
let charDigits = Array(map[currentChar]!)
for i in 0..<charDigits.count {
let newChar = current + "\(charDigits[i])"
combinations_dfs_helper(digits, newChar, index + 1, &output)
}
}
}

Complexity Analysis:

Time Complexity: O(4NN), where N is the length of digits

The worst-case is where the input consists of only 7s and 9s. In that case, we have to explore 4 additional paths for every extra digit. Then, for each combination, it costs up to NN to build the combination. This problem can be generalized to a scenario where numbers correspond with up to MM digits, in which case the time complexity would be O(M^N \cdot N)O(MNN). For the problem constraints, we’re given, M = 4M=4, because of digits 7 and 9 having 4 letters each.

Space Complexity: O(N)

Leave a Reply

Your email address will not be published. Required fields are marked *