首页 > 代码库 > Leetcode17--->Letter Combinations of a Phone Number(电话号码对应的字母的组合)
Leetcode17--->Letter Combinations of a Phone Number(电话号码对应的字母的组合)
题目:
给定一个数字字符串,返回数字所能代表的所有字母组合;
举例:
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
解题思路:
1. 首先要判断给定的数字字符串是否合法(isDigit()方法),即是否只包含0~9的数字,如果还包含其他,则直接返回空;
2. 其次要将每个电话号码所对应的字符串保存起来,这里我使用的是HashMap,key是数字,value是数字所对应的字符串;
3. 采用递归的方式将数字所代表的字母连接起来;举例:234,则对应的是abc,def,ghi,此时首先选择a,然后选择d,然后选择g,得到一个结果adg,选择h,得到一个结果adh,选择i,得到结果adi;选择e.选择g得到结果aeg,以此类推......
代码如下:
1 public class Solution { 2 public List<String> letterCombinations(String digits) { 3 List<String> res = new ArrayList<String>(); 4 if(digits == null || digits.length() < 1){ 5 return res; 6 } 7 if(!isDigit(digits)) return res; 8 HashMap<Character, String> hm = new HashMap<Character, String>(); 9 hm.put(‘0‘, "");10 hm.put(‘1‘, "");11 hm.put(‘7‘, "pqrs");12 hm.put(‘8‘, "tuv");13 hm.put(‘9‘, "wxyz");14 String str = "abcdefghijklmno";15 int i = 2;;16 int j = 0;17 while(i < 7){18 hm.put((char)(i + ‘0‘), str.substring(j, j + 3));19 j = j + 3;20 i++;21 }22 char[] ch = new char[digits.length()];23 isCal(digits, 0, ch, res, hm);24 return res;25 }26 // 判断给定的数字字符串是否合法,不合法,统一返回空27 public boolean isDigit(String digits){28 for(int i = 0; i < digits.length(); i++){29 if(digits.charAt(i) < ‘0‘ || digits.charAt(i) >‘9‘)30 return false;31 }32 return true;33 }
// index代表的是第几个数字34 public void isCal(String digits, int index, char[] ch, List<String> res, HashMap<Character, String> hm){35 if(index == digits.length()){ // 如果成立,表明已经连接到最后一个数字了,因此要将结果加入res36 res.add(new String(ch));37 return;38 }39 char c = digits.charAt(index);40 for(int i = 0; i < hm.get(c).length(); i++){ // 41 ch[index] = hm.get(c).charAt(i); // 获取index所对应数字的字符串中的字符42 isCal(digits, index + 1, ch, res, hm); // 获取下一个数字所对应的字符串中的字符43 }44 45 }46 }
Leetcode17--->Letter Combinations of a Phone Number(电话号码对应的字母的组合)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。