电话号码的字母组合

Tips

题目类型: BackTracking

题目

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

提示:

• 0 <= digits.length <= 4
• digits[i] 是范围 2 - 9 中的一个数字.

示例

输入: digits = "23"

输出: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

题解

JavaScript

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  const res = []

  if (digits.length === 0) return []

  // 写一个 map 来模拟手机键盘
  const map = ['abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']

  const dfs = (track) => {
    const n = track.length

    // 题目要求组合字母的长度要和 digits 的长度相同
    // 此时就可以将 track 收割了
    if (n === digits.length) {
      res.push(track.join(''))
      return
    }

    // 拿到当前数字对应的字母
    const letters = map[Number(digits[n]) - 2]

    // 遍历某个数字对应的字母, 比如 def, 进行回溯
    for (const letter of letters) {
      track.push(letter)
      dfs(track.slice())
      track.pop()
    }
  }

  dfs([])

  return res
}

Rust

pub fn letter_combinations(digits: String) -> Vec<String> {
    let mut res = vec![];

    if digits.len() == 0 {
        return res;
    }

    let digits = digits.as_bytes().iter().fold(vec![], |mut digits, b| {
        digits.push((b - b'0') as usize);
        digits
    });

    let map = vec![
        vec!["a", "b", "c"],
        vec!["d", "e", "f"],
        vec!["g", "h", "i"],
        vec!["j", "k", "l"],
        vec!["m", "n", "o"],
        vec!["p", "q", "r", "s"],
        vec!["t", "u", "v"],
        vec!["w", "x", "y", "z"],
    ];

    dfs(&mut res, &mut vec![], &map, &digits);

    res
}

fn dfs(
    res: &mut Vec<String>,
    track: &mut Vec<String>,
    map: &Vec<Vec<&str>>,
    digits: &Vec<usize>,
) {
    let n = track.len();

    if n == digits.len() {
        res.push(track.join(""));
        return;
    }

    let letters = &map[digits[n] - 2];

    for i in 0..letters.len() {
        track.push(letters[i].to_string());
        dfs(res, track, map, digits);
        track.pop();
    }
}