all articles

leetcode war 17 - Letter Combinations of a Phone Number

2017-10-06 @sunderls

leetCode js

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/

Given a digit string, return all possible letter combinations that the number could represent.

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

analysis

it looks easy.

digit f(digit)
1 -
2 a, b, c
3 d, e, f
4 g, h, i
5 j, k, f
6 m, n, o
7 p, q, r, s
8 t, u, v
9 w, x, y, z
0 -

for 23, 234, we can safely for-loop the possiblities for each digit.

solution 1 - just loop them

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    var letters = {
        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: []
    };

    var result = [];
    var i = j = k = 0;
    var letterArr = null;
    var tmp = null;
    for (total = digits.length; i < total; i++) {
        letterArr = letters[digits[i]];

        // attention the single letter case
        if (i === 0) {
            result = letterArr.slice(0);
        } else {
            for (j = 0, totalJ = result.length; j < totalJ; j++) {
                tmp = result.shift() || '';
                for (k = 0, totalK = letterArr.length; k < totalK; k++) {
                    result.push(tmp + letterArr[k]);
                }
            }            
        }

    }

    return result;
};

well made some mistakes on the one-digit case, but it passed , ranking top 10%.

It seems easy to me, maybe the point it shift and push to reuse the array ? dunno