0017. Letter Combinations of a Phone Number (M)

Letter Combinations of a Phone Number (M)

题目

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

Input: "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.

---

题意

给定一个只包含 2-9 数字的字符串，要求返回由这些数字代表的字母组成的所有排列。

思路

递归回溯法或迭代实现。

---

代码实现

Java

递归

class Solution {
        public List<String> letterCombinations(String digits) {
            // 特殊情况，直接返回空的List
            if (digits.isEmpty()) {
                return new ArrayList<String>();
            }
            String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            List<String> ans = new ArrayList<>();
            generate(digits, map, "", ans);
            return ans;
        }

        private void generate(String digits, String[] map, String s, List<String> ans) {
            // 递归边界，无剩余数字可用说明已经完成了一个排列
            if (digits.isEmpty()) {
                ans.add(s);
                return;
            }
            int first = digits.charAt(0) - '0';
            for (int i = 0; i < map[first].length(); i++) {
                s += map[first].charAt(i);						// 先加入当前字符
                generate(digits.substring(1), map, s, ans);		// 递归处理右侧数字
                s = s.substring(0, s.length() - 1);				// 删除加入的字符
            }
        }
}

迭代

class Solution {
    public List<String> letterCombinations(String digits) {
        if (digits.isEmpty()) {
            return new ArrayList<>();
        }

        String[] map = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        List<String> list = new ArrayList<>();
        list.add("");

        for (int i = 0; i < digits.length(); i++) {
            List<String> temp = new ArrayList<>();
            for (char c : map[digits.charAt(i) - '0'].toCharArray()) {
                for (String s : list) {
                    temp.add(s + c);
                }
            }
            list = temp;
        }

        return list;
    }
}

JavaScript

递归

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  if (digits.length === 0) return []

  let map = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
  let list = []

  dfs(digits.split(''), 0, map, [], list)
  return list
}

let dfs = function (digits, index, map, s, list) {
  if (index === digits.length) {
    return list.push(s.join(''))
  }

  for (let c of map[+digits[index]].split('')) {
    s.push(c)
    dfs(digits, index + 1, map, s, list)
    s.pop()
  }
}

迭代

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function (digits) {
  if (digits.length === 0) return []

  let map = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz']
  let list = ['']

  for (let d of digits) {
    let temp = []
    for (let s of list) {
      for (let c of map[+d].split('')) {
        temp.push(s + c)
      }
    }
    list = temp
  }

  return list
}