17.Letter Combinations of a Phone Number

Description

Hints

Submissions

Discuss

Solution

Pick One

Given a digit string, 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.

Input:
Digit string "23" 

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

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);  
        }


    }


}