手机按键组合，回溯
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.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
1 package com.rust.TestString; 2 3 import java.util.ArrayList; 4 import java.util.List; 5 6 public class LetterCombinationsofaPhoneNumber { 7 public static List<String> letterCombinations(String digits) { 8 List<String> result = new ArrayList<String>(); 9 if (digits.equalsIgnoreCase("")) { 10 return result; 11 } 12 String[] keys = new String[10]; 13 keys[0] = ""; 14 keys[1] = ""; 15 keys[2] = "abc"; 16 keys[3] = "def"; 17 keys[4] = "ghi"; 18 keys[5] = "jkl"; 19 keys[6] = "mno"; 20 keys[7] = "pqrs"; 21 keys[8] = "tuv"; 22 keys[9] = "wxyz"; 23 char[] temp = new char[digits.length()]; 24 combine(keys, temp, digits, 0, result); 25 return result; 26 } 27 public static void combine(String[] keys, char[] temp, String digits, int index, List<String> res) { 28 if (index == digits.length()) { 29 res.add(new String(temp)); 30 return; // get out now 31 } 32 char digitChar = digits.charAt(index); 33 for (int i = 0; i < keys[digitChar - '0'].length(); i++) { // scan char at keys[digitChar - '0'] 34 temp[index] = keys[digitChar - '0'].charAt(i); 35 combine(keys, temp, digits, index + 1, res); 36 } 37 38 } 39 public static void main(String args[]){ 40 List<String> one = letterCombinations(""); 41 for (int i = 0; i < one.size(); i++) { 42 System.out.print(one.get(i)+" "); 43 } 44 } 45 }
