17 Letter Combinations of a Phone Number

　手機(jī)上每個(gè)數(shù)字按鈕旁邊都有3-4個(gè)字母，輸入數(shù)字字符串，輸出可能的字母組合。
　例如輸入：”23”
　輸出：[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
　思路：建立每個(gè)數(shù)字和對(duì)應(yīng)字母的映射關(guān)系。該個(gè)處理每一位數(shù)字，遍歷每個(gè)數(shù)字可能的取值。按照遞歸去實(shí)現(xiàn)很簡(jiǎn)單。
　

private List<String> result = new ArrayList<String>(); private static Map<Integer, List<Character>> numberMap = new HashMap<Integer, List<Character>>(); static{for(int i=2;i<7;i++){numberMap.put(i, new ArrayList<Character>());for (int j = 0; j < 3; j++) {char ch = (char) ('a' + 3 * (i - 2) + j);numberMap.get(i).add(ch);}}numberMap.put(7, new ArrayList<Character>());numberMap.get(7).add('p');numberMap.get(7).add('q');numberMap.get(7).add('r');numberMap.get(7).add('s');numberMap.put(8, new ArrayList<Character>());numberMap.get(8).add('t');numberMap.get(8).add('u');numberMap.get(8).add('v');numberMap.put(9, new ArrayList<Character>());numberMap.get(9).add('w');numberMap.get(9).add('x');numberMap.get(9).add('y');numberMap.get(9).add('z');} public List<String> letterCombinations(String digits) {result.clear();StringBuilder str = new StringBuilder(digits.length());str.setLength(digits.length());if(digits.length()>0){robot(0, digits, str);}return result; }private void robot(int idx, String digits, StringBuilder r) {if (idx >= digits.length()) {result.add(r.toString());return;}int n = digits.charAt(idx) - 48;if (n < 2)return;for(char ch : numberMap.get(n)){r.setCharAt(idx, ch);robot(idx + 1, digits, r);} }

收獲1

　嗯代碼夠丑的。看別人怎么處理映射關(guān)系。我怎么沒(méi)想到呢。之前也有這樣一個(gè)例子，當(dāng)數(shù)字作為map的key的時(shí)候，選擇用數(shù)組代替map，可能會(huì)是一種比較優(yōu)雅的方式。
　

String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

收獲２

　一次性給stringBuider 一定的長(zhǎng)度。這個(gè)做法在字符串中還是有點(diǎn)變扭。這個(gè)想法是從數(shù)組那里繼承過(guò)來(lái)的。可以使用字符串相加的方式。
　

private static final String[] KEYS = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; private List<String> result = new ArrayList<String>();public List<String> letterCombinations(String digits) {result.clear();robot(0, digits, "");return result; }private void robot(int idx, String digits, String prefix) {if (idx >= digits.length()) {if (prefix.length() > 0) {result.add(prefix);}return;}int n = digits.charAt(idx) - 48;if (n < 2)return;String letters = KEYS[n];for (int i = 0; i < letters.length(); i++) {robot(idx + 1, digits, prefix + letters.charAt(i));} }

收獲3

　我是沒(méi)法用遞推的方式實(shí)現(xiàn)的，只能用遞歸。看看別人怎么做。其實(shí)從上一個(gè)遞歸的代碼是可以得到一些啟示的。當(dāng)然這是“馬后炮”的想法–看到別人這么做覺(jué)得應(yīng)該想到的。但是之前我一直在用for去思考。
　

public List<String> letterCombinations(String digits) {LinkedList<String> ans = new LinkedList<String>();String[] mapping = new String[] { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };ans.add("");for (int i = 0; i < digits.length(); i++) {int x = Character.getNumericValue(digits.charAt(i));while (ans.peek().length() == i) {String t = ans.remove();for (char s : mapping[x].toCharArray())ans.add(t + s);}}return ans;}

參考鏈接
1 鏈接1　
2 鏈接2

總結(jié)

以上是生活随笔為你收集整理的leetcode之回溯backtracing专题3的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。