题目描述

原题链接

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：
输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

示例 2：
输入：digits = “”
输出：[]

示例 3：
输入：digits = “2”
输出：[“a”,”b”,”c”]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 [‘2’, ‘9’] 的一个数字。

个人解法

JavaScript

const phoneObj = {
  '2': 'abc',
  '3': 'def',
  '4': 'ghi',
  '5': 'jkl',
  '6': 'mno',
  '7': 'pqrs',
  '8': 'tuv',
  '9': 'wxyz',
}
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  if (digits.length === 0) {
    return [];
  }
  let result = [...phoneObj[digits[0]]];
  const len = digits.length;
  for (let i = 1; i < len; i++) {
    const str = phoneObj[digits[i]];
    let temp = [];
    for (let j = 0; j < str.length; j++) {
      const resLen = result.length;
      for (let k = 0; k < resLen; k++) {
        temp.push(result[k] + str[j]);
      }
    }
    result = temp;
  }
  return result;
};

Java

class Solution {
    public List<String> letterCombinations(String digits) {
        char[] digit=digits.toCharArray();
        List<String> lists=new ArrayList<>();
        int l= digit.length;
        if (l==0){
            return lists;
        }else {
            return def(digit,0,lists,l);
        }
    }
    public static List<String> def(char[] digit, int n, List<String> lists, int l) {
        int x = (int) digit[n] - 48;
        char[] results=null;
        if (x == 7) {
            results = new char[]{'p', 'q', 'r', 's'};
        } else if (x == 8) {
            results = new char[]{'t', 'u', 'v'};
        } else if (x == 9) {
            results = new char[]{'w', 'x', 'y', 'z'};
        } else {
            results = new char[]{(char) (3 * x + 91), (char) (3 * x + 92), (char) (3 * x + 93)};
        }
        List<String> list1 = new ArrayList<>();
        String r = null;
        int len= results.length;
        if (lists.size() == 0) {
            for (int j = 0; j < len; j++) {
                r = "" + results[j];
                list1.add(r);
            }
        } else {
            for (int i = 0; i < lists.size(); i++) {
                for (int j = 0; j < len; j++) {
                    r = lists.get(i) + results[j];
                    list1.add(r);
                }
            }
        }
        if (n == l - 1) {
            return list1;
        } else {
            return def(digit, n + 1, list1, l);
        }
    }
}

更优解法

Java

JavaScript

const letterCombinations = (digits) => {
  if (digits.length == 0) return [];
  const map = { '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz' };
  const queue = [];
  queue.push('');
  for (let i = 0; i < digits.length; i++) { // bfs的层数，即digits的长度
    const levelSize = queue.length;         // 当前层的节点个数
    for (let j = 0; j < levelSize; j++) {   // 逐个让当前层的节点出列
      const curStr = queue.shift();         // 出列
      const letters = map[digits[i]];       
      for (const l of letters) {
        queue.push(curStr + l); // 生成新的字母串入列
      }
    }
  }
  return queue; // 队列中全是最后一层生成的字母串
};