Friday, April 11, 2014

LeetCode: Letter Combinations of a Phone Number

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"].

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


A easy problem. Do DFS to construct the results.

C++ Code:

/*
 * func: letter_combinations_helper
 * goal: DFS search function to construct results
 * @param digits: remaining digits string
 * @param output: current output string
 * @param result: result set
 * return: no return value needed
 */
void letter_combinations_helper(string digits, string output, vector<string> &result,){
    if(digits.size() == 0){
        //No more digits reading need
        result.emplace_back(output);
        return;
    }
    switch(digits[0]){
        case '2':
            letter_combinations(digits.substr(1), result, output + 'a');
            letter_combinations(digits.substr(1), result, output + 'b');
            letter_combinations(digits.substr(1), result, output + 'c');
            break;
        case '3':
            letter_combinations(digits.substr(1), result, output + 'd');
            letter_combinations(digits.substr(1), result, output + 'e');
            letter_combinations(digits.substr(1), result, output + 'f');
            break;
        case '4':
            letter_combinations(digits.substr(1), result, output + 'g');
            letter_combinations(digits.substr(1), result, output + 'h');
            letter_combinations(digits.substr(1), result, output + 'i');
            break;
        case '5':
            letter_combinations(digits.substr(1), result, output + 'j');
            letter_combinations(digits.substr(1), result, output + 'k');
            letter_combinations(digits.substr(1), result, output + 'l');
            break;
        case '6':
            letter_combinations(digits.substr(1), result, output + 'm');
            letter_combinations(digits.substr(1), result, output + 'n');
            letter_combinations(digits.substr(1), result, output + 'o');
            break;
        case '7':
            letter_combinations(digits.substr(1), result, output + 'p');
            letter_combinations(digits.substr(1), result, output + 'q');
            letter_combinations(digits.substr(1), result, output + 'r');
            letter_combinations(digits.substr(1), result, output + 's');
            break;
        case '8':
            letter_combinations(digits.substr(1), result, output + 't');
            letter_combinations(digits.substr(1), result, output + 'u');
            letter_combinations(digits.substr(1), result, output + 'v');
            break;
        case '9':
            letter_combinations(digits.substr(1), result, output + 'w');
            letter_combinations(digits.substr(1), result, output + 'x');
            letter_combinations(digits.substr(1), result, output + 'y');
            letter_combinations(digits.substr(1), result, output + 'z');
            break;
        default:
            letter_combinations(digits.substr(1), result, output);
            break;
    }
}

/*
 * func: letter_combinations_helper
 * goal: to find all possible combinations based on input digits
 * @param digits: input digits string
 * return: vector containing all possible combinations
 */
vector<string> letter_combinations(string digits) {
    vector<string> result;
    letter_combinations_helper(digits, "", result,);
    return result;
}

Python Code:

# func: to find all possible combinations based on input digits
# @param digits: input digits string
# @return: all possible combinations
def letter_combinations(digits):
    num_dict = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno',
    '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    result = ['']
    for digit in digits:
        if digit in '23456789':
            result = [x + letter for x in result for letter in num_dict[digit]]
            
    return result

No comments:

Post a Comment