1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| class Solution { Map<String, String> phone = new HashMap<String, String>() {{ 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<String> output = new ArrayList<String>();
public void backtrack(String combination, String next_digits) { // if there is no more digits to check if (next_digits.length() == 0) { // the combination is done output.add(combination); } // if there are still digits to check else { // iterate over all letters which map // the next available digit 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); // append the current letter to the combination // and proceed to the next digits // letter往后一直移动是因为从a到b,b到c, c到d。。。这样 backtrack(combination + letter, next_digits.substring(1)); // backtrack(letter + combination, next_digit.substring(1)); //Output ["da","ea","fa","db","eb","fb","dc","ec","fc"] } } }
public List<String> letterCombinations(String digits) { if (digits.length() != 0) backtrack("", digits); return output; } }
|