本文共 1610 字，大约阅读时间需要 5 分钟。

题目

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.

Input: “23”

Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

思路

先用HashMap把键盘上的键值对存起来。但是怎样拼凑每个子字符串呢？肯定不能用brute force来解，输入稍微多一点就崩了。递归？subStr += recur()？

解答

leetcode solution 1: Backtracking(DFS) 回溯算法：

class Solution {
     Map
   
     phone = new HashMap
    
     () {
   {
       put("2", "abc");    put("3", "def");    put("4", "ghi");    put("5", "jkl");    put("6", "mno");    put("7", "pqrs");    put("8", "tuv");    put("9", "wxyz");  }};//匿名内部类初始化  List
     
       output = new ArrayList
      
       ();  public void backtrack(String combination, String next_digits) {
       // if there is no more digits to check    if (next_digits.length() == 0) {
         output.add(combination);    }    // if there are still digits to check    else {
         String digit = next_digits.substring(0, 1);      String letters = phone.get(digit);      for (int i = 0; i < letters.length(); i++) {
           String letter = phone.get(digit).substring(i, i + 1);        backtrack(combination + letter, next_digits.substring(1));        // substring(n); 取从n到最后一位元素为子串      }    }  }  public List
       
         letterCombinations(String digits) {
       if (digits.length() != 0)      backtrack("", digits);    return output;  }}
       
      
     
    
   

一些思考

遇到Brute Force会变成指数型复杂度的问题，就想到DFS、BFS这种递归算法

转载地址：http://bfqvb.baihongyu.com/