每日一道算法题——Letter Combinations of a Phone Number

2019-11-08 18:50:35

字体：大中小

来源：转载

供稿：网友

电话号码的字母组合

题目

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.

number

Input:Digit string "23"Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

分析

随机按一串数字，给出这些号码所有可能的字符排列。为了不产生歧义，我给出下面各个号码代表的字符

{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}

算法

这题用回溯法是很好写的。直接上代码：

public class Solution { public List<String> letterCombinations(String digits) { if(digits.length()<1) return new LinkedList<String>(); LinkedList<String> ans = new LinkedList<String>(); String[] mapping = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; backTrack(digits,0,"",mapping,ans); return ans; } public void backTrack(String digits,int k,String s,String[] mapping ,LinkedList<String> ans){ //结束条件 if(k>=digits.length()){ ans.add(s); return; } String c = mapping[digits.charAt(k)-'0'];//得到按键的值 for(int i=0;i<c.length();i++){ s+=c.charAt(i)+"";//把字符c.charAt(i)追加到末尾 backTrack(digits,k+1,s,mapping,ans);//递归下一个按键 s = s.substring(0,s.length()-1);//恢复 } return; }}

所以一般排列问题大家都可以先想想回溯法，毕竟代码实现是很容易的。

上一篇：安卓自定义控件--垂直进度条

下一篇：一分钟了解负载均衡的一切