[LeetCode] 17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

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

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

Analyse:

遞迴解法.

Solution:

class Solution {
 
    let numToLetters = [
        "1": ["1"],
        "2": ["a", "b", "c"],
        "3": ["d", "e", "f"],
        "4": ["g", "h", "i"],
        "5": ["j", "k", "l"],
        "6": ["m", "n", "o"],
        "7": ["p", "q", "r", "s"],
        "8": ["t", "u", "v"],
        "9": ["w", "x", "y", "z"],
        "0": ["0"]
    ]
    
    func letterCombinations(_ digits: String) -> [String] {
       var chars = Array(digits);
       var output: [String] = [];
        
       handler(chars, "", &output);   
        
       return output;
    } 
    
    func handler(_ chars: [Character], _ text: String, _ output: inout [String]) {
        if(chars.count == 0) {
            if(text != "") {
                output.append(text);
            }
            return;
        }
        

        let char = String(chars[0]);
        let letters = numToLetters[char]!
        
        var newChars = chars;
        newChars.remove(at: 0);
        
        for i in 0..<letters.count {
            handler(newChars, text+String(letters[i]), &output);  
        }  
    } 
}