blog.image

[LeetCode][Medium] 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. Return the answer in any order.

題目

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.

alt

思路

寫一個縫合矩陣的函式,然後把數字字串輸入,合成出最終結果。

Solution

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

    if (digits.length < 2) return letterMap[digits]
    
    let res = []
    
    for (var i = 0; i < digits.length; i++) {
        res = zip(res, letterMap[digits[i]])
    }
    return res
};

var zip = function(a, b) {
    const res = []
    if (a.length < 1) return b
    
    for (var i = 0; i < a.length; i++) {
        for(var j = 0; j < b.length; j++) {
            res.push(a[i] + b[j])
        }
    }
    return res
}

Complexity

  • Time complexity : O(n^2)
  • Space complexity : O(n)

類似文章

record.image

Engineering

[LeetCode][Medium] 19. Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

author.image
1 min
record.image

Engineering

[LeetCode][Medium] 15. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

author.image
1 min