Letter Combinations of a Phone Number

描述

Given a digit string, 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.

Phone Keyboard

Figure: Phone Keyboard

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

分析

无

递归

  1. // Letter Combinations of a Phone Number
  2. // 时间复杂度O(3^n)，空间复杂度O(n)
  3. public class Solution {
  4.     private static final String[] keyboard =
  5.             new String[]{ " ", "", "abc", "def", // '0','1','2',...
  6.             "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
  8.     public List<String> letterCombinations(String digits) {
  9.         List<String> result = new ArrayList<>();
  10.         if (digits.isEmpty()) return result;
  11.         dfs(digits, 0, "", result);
  12.         return result;
  13.     }
  15.     private static void dfs(String digits, int cur, String path,
  16.                             List<String> result) {
  17.         if (cur == digits.length()) {
  18.             result.add(path);
  19.             return;
  20.         }
  21.         final String str = keyboard[digits.charAt(cur) - '0'];
  23.         for (char c : keyboard[digits.charAt(cur) - '0'].toCharArray()) {
  24.             dfs(digits, cur + 1, path + c, result);
  25.         }
  26.     }
  27. }

迭代

  1. // Letter Combinations of a Phone Number
  2. // 时间复杂度O(3^n)，空间复杂度O(1)
  3. public class Solution {
  4.     private static final String[] keyboard =
  5.             new String[]{ " ", "", "abc", "def", // '0','1','2',...
  6.                     "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
  8.     public List<String> letterCombinations(String digits) {
  9.         if (digits.isEmpty()) return new ArrayList<>();
  10.         List<String> result = new ArrayList<>();
  11.         result.add("");
  12.         for (char d : digits.toCharArray()) {
  13.             final int n = result.size();
  14.             final int m = keyboard[d - '0'].length();
  16.             // resize to n * m
  17.             for (int i = 1; i < m; ++i) {
  18.                 for (int j = 0; j < n; ++j) {
  19.                     result.add(result.get(j));
  20.                 }
  21.             }
  23.             for (int i = 0; i < result.size(); ++i) {
  24.                 result.set(i, result.get(i) + keyboard[d - '0'].charAt(i/n));
  25.             }
  26.         }
  27.         return result;
  28.     }
  29. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/brute-force/letter-combinations-of-a-phone-number.html