LetterCombinationsOfAPhoneNumber [source code]
public class LetterCombinationsOfAPhoneNumber {
static
/******************************************************************************/
class Solution {
static char[][] letters = {
{' '},
{'1'},
{'a', 'b', 'c'},
{'d', 'e', 'f'},
{'g', 'h', 'i'},
{'j', 'k', 'l'},
{'m', 'n', 'o'},
{'p', 'q', 'r', 's'},
{'t', 'u', 'v'},
{'w', 'x', 'y', 'z'},
};
public List<String> letterCombinations(String _digits) {
char[] digits = _digits.toCharArray ();
List<String> res = new ArrayList<> ();
if (digits.length == 0)
return res;
return convert (dfs (digits, 0));
}
List<Deque<Character>> dfs (char[] digits, int index) {
if (index == digits.length)
return new ArrayList<> (); // don't add type parameter here;
assert Character.isDigit (digits[index]);
int digit = digits[index] - '0';
char[] button = letters[digit];
List<Deque<Character>> res = new ArrayList<> (), res_right = dfs (digits, index + 1);
for (Character c : button) {
if (res_right.isEmpty ()) {
Deque<Character> deq = new ArrayDeque<> ();
deq.push (c);
res.add (deq);
} else {
for (Deque<Character> path : res_right) {
path.push (c);
res.add (new ArrayDeque<> (path));
path.pop ();
}
}
}
return res;
}
List<String> convert (List<Deque<Character>> ls) {
List<String> res = new ArrayList<> ();
for (Deque<Character> deq : ls) {
StringBuilder sb = new StringBuilder ();
while (!deq.isEmpty ())
sb.append (deq.pop ());
res.add (sb.toString ());
}
return res;
}
}
/******************************************************************************/
public static void main(String[] args) {
LetterCombinationsOfAPhoneNumber.Solution tester = new LetterCombinationsOfAPhoneNumber.Solution();
String[][] inputs = {
{"23"}, {"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"},
};
for (int i = 0; i < inputs.length / 2; i++) {
String digits = inputs[2 * i][0];
Set<String> ans = new HashSet<> (Arrays.asList (inputs[2 * i + 1]));
System.out.println (Printer.separator ());
Set<String> output = new HashSet<> (tester.letterCombinations (digits));
System.out.printf ("%s -> %s, expected: %s\n",
digits, Printer.wrapColor (output.toString (), output.equals (ans) ? "green" : "red"), ans
);
}
}
}
看起来好像不难, 先随便乱写一个;
大概还是写出来了, 不过各种接口用的时候还是错误百出; 一个重要的内容, 是比如ArrayDeque, HashSet这样的东西的constructor, 是几乎只接受其他的collection的. 所以不要指望直接丢一个element或者一个array给他, 他会自动转化; 比如res.add (new ArrayDeque<> (c));这个就是错的; 最坑的是, 这个你写出来, 他不会报错! 因为这些class的constructor都有一个take int的, 这个int被认为是num_elements什么的; 所以这里就是char直接被convert到int了;
这个东西还适用于下面的StringBuilder! 没想到吧, 也就是说new StringBuilder (c), 是不行的, 只能用string;
除开这个以外, 好像其他的大部分的时候都是能infer就让他自己infer type parameter, 当然前提是你的左值的type/interface里面的type parameter要很明确;
另外这个题目有点奇怪, 我本来是准备对1进行特殊处理的: 在我的static的表里面, 我给1就是自己, 然后我准备在最后convert的时候, 看到1就跳过, 这样就行; 但是结果发现直接AC了, 原来OJ好像根本不接受所有有1的case, 我试了一下, 全都是返回Empty; 所以那就懒得加了;
这题我本来是觉得用Deque这些东西, 可能最后速度会有所提高, 避免传string, 但是后面发现根本就很坑, 速度只有8ms (3%). 还是Jason那句话, 这种collection of collections真的很慢;
后来用StringBuilder写了一个:
class Solution {
static char[][] letters = {
{' '},
{'1'},
{'a', 'b', 'c'},
{'d', 'e', 'f'},
{'g', 'h', 'i'},
{'j', 'k', 'l'},
{'m', 'n', 'o'},
{'p', 'q', 'r', 's'},
{'t', 'u', 'v'},
{'w', 'x', 'y', 'z'},
};
public List<String> letterCombinations(String _digits) {
char[] digits = _digits.toCharArray ();
List<String> res = new ArrayList<> ();
if (digits.length == 0)
return res;
return convert (dfs (digits, 0));
}
List<StringBuilder> dfs (char[] digits, int index) {
if (index == digits.length)
return new ArrayList<> (); // don't add type parameter here;
assert Character.isDigit (digits[index]);
int digit = digits[index] - '0';
char[] button = letters[digit];
List<StringBuilder> res = new ArrayList<> (), res_right = dfs (digits, index + 1);
for (Character c : button) {
if (res_right.isEmpty ()) {
res.add (new StringBuilder (String.valueOf (c)));
} else {
for (StringBuilder path : res_right) {
StringBuilder new_path = new StringBuilder (path);
new_path.append (c);
res.add (new_path);
}
}
}
return res;
}
List<String> convert (List<StringBuilder> ls) {
List<String> res = new ArrayList<> ();
for (StringBuilder sb : ls) {
sb.reverse ();
res.add (sb.toString ());
}
return res;
}
}
但是事实上还是很慢;
这里一个需要学习的东西:
copy by constructing
StringBuilder new_path = new StringBuilder (path);这里, 一开始我查文档, 好像是没有这个StringBuilder自己当参数的, 但是最后试了一下, 也搜了一下StackOverflow, 这个用法居然是可以的, 也不知道是什么鬼; 反正用法类似也是跟collection差不多; 注意StringBuilder这里, 用clone是不行的, 说是什么protected;
没有editorial;
discussion最优解:
@lirensun said in My java solution with FIFO queue:
public List<String> letterCombinations(String digits) {
LinkedList<String> ans = new LinkedList<String>();
if(digits.isEmpty()) return ans;
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;
}
注意看, 这个算法是一个iterative的算法! 事实上, 这题确实是完全可以用循环来做的, 因为你是知道digit位数的;
另外, 他这里这个逻辑真的是极尽精简, 尤其是这个while循环的使用, 非常的简练;
@yellowstone said in My java solution with FIFO queue:
Very good solution!! Thumb up!
This is a iterative solution. For each digit added, remove and copy every element in the queue and add the possible letter to each element, then add the updated elements back into queue again. Repeat this procedure until all the digits are iterated.I did a experiment to compare backtracking(DFS) method and this iterative method. It turns out iterative one is 4 times faster.
One minor bug here.
We need to add some code to test whether the input is empty or not.
Above ans.add("");
addif (digits.length()==0){
return ans;
}
没话说了, 确实, 他的逻辑跟我写的这个DFS是非常类似的, 但是最后速度肯定是比我的快的多的;
@rainhacker said in My java solution with FIFO queue:
ink about the recursive soluti
其实有点道理;
这个是一个更加明显的BFS写法了:
@cdai said in My java solution with FIFO queue:
Thanks for sharing! I assume one of the outer loop could be saved, right?
1. Stop if we find top str in queue is of length as digits 2. Decide which digit to map by length of str in queue
public List<String> letterCombinations(String digits) {
if (digits.isEmpty()) return new ArrayList<>();
String[] map = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
LinkedList<String> q = new LinkedList<>();
q.offer("");
while (!q.isEmpty()) {
if (q.peek().length() == digits.length()) break;
String s = q.poll();
for (char c : map[digits.charAt(s.length()) - '0'].toCharArray())
q.offer(s + c);
}
return q;
}
这个题目其实是一个相当经典的题型, 就是以前见过的一个类似掷骰子的题目类型; 常规的方法是recursion, 上面那个queue的解法, 其实本质上也是recursion, 不过这一题正好有一个比较聪明的BFS写法而已;
这个题目你看到, 应该能想到, 这个其实最简单的思路就是一个N层的循环就可以; 但是因为我们不知道循环层数N, 所以只能用recursion来做.
但是是真的只能用recursion来做吗?
刚才那个帖子下面有一个用纯粹的iteration来做的:
@simkieu said in My java solution with FIFO queue:
I have a different approach and it is more intuitive to me. This is similar to printing all numbers with k digits. For example k=3, you start at 000, then you keep coming up: 001, 002, 003, ... until you reach 009, then reset last bit, and increase the next bit to 010, then 011, 012, etc.
So we can solve this problem in a similar way. If our input string is "23". Because 2 = "abc", 3 = "def", we can start from the smallest "ad", then go up: "ae", "af", then we have to reset last char from "f" to "d" and we have "bd", "be", "bf", etc. This way, we don't need backtracking, recursive, or List.
Hope this helps for some people.
vector<string> letterCombinations(string digits) {
vector<string> R;
if (digits.empty()) return R;
string a[8] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
int n = digits.size();
vector<int> v(n, 0);
// Initialize string V
string S = "";
for (int i=0; i<n; i++)
S += a[digits[i]-'0'-2][0];
while (true) {
R.push_back(S);
int j = n-1;
v[j]++;
while (j>0 && v[j]==a[digits[j]-'0'-2].size()) {
v[j] = 0;
S[j] = a[digits[j]-'0'-2][0];
v[--j]++;
}
//Check to see if outta range yet
if (v[0]==a[digits[0]-'0'-2].size()) break;
else S[0] = a[digits[0]-'0'-2][v[0]];
S[j] = a[digits[j]-'0'-2][v[j]];
}
return R;
}
思路是非常优秀的, 不过这个人的代码写的相当丑;
我用java改写了一下他的思路:
class Solution {
static char[][] mapping = {
{' '},
{'1'},
{'a', 'b', 'c'},
{'d', 'e', 'f'},
{'g', 'h', 'i'},
{'j', 'k', 'l'},
{'m', 'n', 'o'},
{'p', 'q', 'r', 's'},
{'t', 'u', 'v'},
{'w', 'x', 'y', 'z'},
};
public List<String> letterCombinations(String _digits) {
char[] digits = _digits.toCharArray ();
int N = digits.length;
List<String> res = new ArrayList<> ();
if (N == 0)
return res;
char[] letters = new char[N];
for (int i = 0; i < N; i++)
letters[i] = mapping[digits[i] - '0'][0];
int[] nums = new int[N];
search: while (true) {
res.add (new String (letters));
int i = N - 1;
while (++nums[i] == mapping[digits[i] - '0'].length) {
if (i == 0)
break search;
letters[i] = mapping[digits[i] - '0'][nums[i--] = 0];
}
letters[i] = mapping[digits[i] - '0'][nums[i]];
}
return res;
}
}
速度达到了3(68), 很好. 不过我这个代码其实写的也挺难懂的, 还用了label; 顺便, 看看这个: https://docs.oracle.com/javase/tutorial/java/nutsandbolts/branch.html .这个帖子教了一下java里面label的用法, 跟c还是有点区别的, 不过不是特别难;
有空好好看看我的写的这个代码, 不是那么trivial的; 另外, 这个程序就是展示了这种用carried addition来模拟unknown depth iteration的思路; 这个其实跟以前见过的一个binary enumeration很像, 不过这里的实现相对复杂一些; 一个小的细节就是, 你看我把increment写到了while循环的header里面; 以及, 为什么这里必须用while? 实际上这一题用if是可以的, 因为这里所有的length都是超过1的, 但是广义上来说, 用while更正确: 一次进位可能导致连锁效应;
总体来说我觉得我这个程序写的比他的赏心悦目很多;
另外, 如果这题有人问你复杂度, 是4^N, 不能说3^N, 低级错误; 适合于大部分目前见到的算法, 毕竟都是搜索;
一个正常的写法:
@peerlessbloom said in My iterative sollution, very simple under 15 lines:
This is my solution, FYI
vector<string> letterCombinations(string digits) {
vector<string> res;
string charmap[10] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
res.push_back("");
for (int i = 0; i < digits.size(); i++)
{
vector<string> tempres;
string chars = charmap[digits[i] - '0'];
for (int c = 0; c < chars.size();c++)
for (int j = 0; j < res.size();j++)
tempres.push_back(res[j]+chars[c]);
res = tempres;
}
return res;
}
下面有人回复:
@mileschen2008 said in My iterative sollution, very simple under 15 lines:
I think the time complexity is too high compared to the backtracking method because for each digit you must traverse the vector res, which adds additional complexity.
好像是对的, 这个可能才是为什么我的思路这么慢的真正的原因; 我的思路其实跟他这个写法是没有区别的; 这个对之前的res的iteration, 大大的增加了复杂度; 不对! 还是正常的指数级别! 这个做法的recurrence关系其实就是, 你看这个循环:
for (int c = 0; c < chars.size();c++)
for (int j = 0; j < res.size();j++)
这个其实就是在之前的结果的基础上乘以一个3或者4的关系, 所以几个循环下来, 就是一个4^N的关系而已;
不过这里也交代了一个坑, 就是有些算法虽然写起来是一个循环的形式, 但是分析的时候还是要借助于recurrence; 这里主要是因为这个res size并不是那么直观的常量, 你用简单的循环的方式去分析未必有效果; 关键脑子里还是要有一个动态的trace, 不然分析复杂度的时候可能会太naive;
这个是一个写的很规整的backtracking:
@luming.zhang.75 said in 8-line Backtracking-Function C++ Solution:
Most concise backtracking function, no?
class Solution {
public:
vector<string> letterCombinations(string digits)
{
vector<string> res;
if(digits.size()==0) return res;
string local;
vector<vector<char>> table(2,vector<char>());
table.push_back(vector<char>{'a','b','c'}); // index 2
table.push_back(vector<char>{'d','e','f'}); // 3
table.push_back(vector<char>{'g','h','i'});
table.push_back(vector<char>{'j','k','l'}); // 5
table.push_back(vector<char>{'m','n','o'});
table.push_back(vector<char>{'p','q','r','s'}); // 7
table.push_back(vector<char>{'t','u','v'});
table.push_back(vector<char>{'w','x','y','z'}); // 9
backtracking(table,res,local,0,digits);
return res;
}
void backtracking(const vector<vector<char>>& table, vector<string>& res, string& local, int index, const string& digits) {
if(index==digits.size())
res.push_back(local);
else
for(int i=0;i<table[digits[index]-'0'].size();i++) {
local.push_back(table[digits[index]-'0'][i]);
backtracking(table, res, local, index+1, digits);
local.pop_back();
}
}
};
这个就是按照之前有一道题目看到的一个总结, 最标准的方法写的一个backtracking;
一个小的技巧:
@redace85 said in 8-line Backtracking-Function C++ Solution:
u could get the index from partial result, so four arguments 4 the backtracking function will be enough. just some personal opinion. your solution is quite nice.the difference is slight.
class Solution {
public:
vector<string> letterCombinations(string digits) {
vector<string> ret;
if(0>=digits.size()) return ret;
const string map[]={"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
backTrackingFun(map,digits,"",ret);
return ret;
}
void backTrackingFun(const string m[], const string &digits, string r, vector<string> &ret){
int c=r.size();
if(digits.size()==c){
ret.push_back(r);
return;
}
auto str = m[digits.at(c)-48];
for(auto it=str.cbegin();it!=str.cend();++it){
r.push_back(*it);
backTrackingFun(m,digits,r,ret);
r.pop_back();
}
}
};
submission基本是波动;
Problem Description
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.
Difficulty:Medium
Total Accepted:208.7K
Total Submissions:581.4K
Contributor:LeetCode
Companies
googlefacebookamazonuberdropbox
Related Topics
stringbacktracking
Similar Questions
Generate ParenthesesCombination SumBinary Watch