[LeetCode 17]Letter Combinations of a Phone Number

题目链接：letter-combinations-of-a-phone-number

import java.util.ArrayList;import java.util.Arrays;import java.util.List;/** * 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"].Note:Although the above answer is in lexicographical order, your answer could be in any order you want. * */public class LetterCombinationsOfAPhoneNumber {public static String[] mapping = new String[] {"", "", "abc", "def","ghi", "jkl", "mno","pqrs", "tuv", "wxyz"};//解法一：递归法// 25 / 25 test cases passed.// Status: Accepted// Runtime: 208 ms// Submitted: 0 minutes agostatic List<String> letterCombinations1(String digits) {List<String> combinations = new ArrayList<String>();dfs(digits, "", combinations);return combinations; } static void dfs(String digits, String path, List<String> combinations) { if(digits.length() == 0) return; else if(digits.length() == 1) {for(Character letter : mapping[digits.charAt(0) – '0'].toCharArray()) {combinations.add(path + letter);} } else {for(Character letter : mapping[digits.charAt(0) – '0'].toCharArray()) {dfs(digits.substring(1), path + letter, combinations);} } }//解法二：遍历法 // 25 / 25 test cases passed.// Status: Accepted// Runtime: 211 ms// Submitted: 0 minutes agostatic List<String> letterCombinations(String digits) {List<String> combinations = new ArrayList<String>();if(digits.length() == 0) return combinations;for (Character c : digits.toCharArray()) {String letters = mapping[c – '0'];if(combinations.size() == 0) {for (Character letter : letters.toCharArray()) {combinations.add(letter + "");}} else {int length = combinations.size();for (Character letter : letters.toCharArray()) {for(int i = 0; i < length; i ++) {String before = combinations.get(i);combinations.add(before + letter);}}for (int i = 0; i < length; i++) {combinations.remove(0);}}}return combinations;}public static void main(String[] args) {System.out.println(Arrays.toString(letterCombinations("234").toArray()));}}

，那么前世我的目光一定一刻都没从你身上离开过吧！