描述

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”].

思路

思路比较简单，就是不断做笛卡尔积。

代码

class Solution { public: vector<string> letterCombinations(string digits) { vector<string> combineVec; if(digits.empty()) return combineVec; static const string letterMap[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; combineVec.push_back(""); int index; for(int i = 0; i < digits.size(); i++){ index = digits[i] - '0'; if(index < 2 || index > 9) continue; vector<string> temp; const string& letterMapValue = letterMap[index]; for(int j = 0; j < combineVec.size();j++){ for(int k = 0; k < letterMapValue.size(); k++){ temp.push_back(combineVec[j] + letterMapValue[k]); } } combineVec=temp; } return combineVec; } };

结果

他山之玉

C++ O(n) solutioin

vector<string> letterCombinations(string digits) { vector<string> result; if(digits.empty()) return vector<string>(); static const vector<string> v = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; result.push_back(""); // add a seed for the initial case for(int i = 0 ; i < digits.size(); ++i) { int num = digits[i]-'0'; if(num < 0 || num > 9) break; const string& candidate = v[num]; if(candidate.empty()) continue; vector<string> tmp; for(int j = 0 ; j < candidate.size() ; ++j) { for(int k = 0 ; k < result.size() ; ++k) { tmp.push_back(result[k] + candidate[j]); } } result.swap(tmp); } return result; }

在第二句的时候，我用的是digits.size()来判断是否为空，结果时间差了2ms。这个地方下次要注意了。

Java O(n) solution

public class Solution { public List<String> letterCombinations(String digits) { List<String> list = new ArrayList<>(); if (digits == null || digits.trim().length() == 0) return list; String[] str = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; char[] ch = digits.trim().toCharArray(); int sum = 1; String [] arr = new String[ch.length]; for (int i = 0; i < ch.length; i++) { arr[i] = str[ch[i] - '0']; } list = new ArrayList<>(sum); return combination(arr, list, 0, ""); } private List<String> combination(String[] s, List<String> list, int index, String result) { if (result.length() == s.length) { list.add(result); return list; } for (int i = index; i < s.length; i++) { for (int j = 0; j < s[i].length(); j++) { combination(s,list, i + 1, result + s[i].substring(j, j + 1)); } } return list; }

这个是利用递归来做的笛卡尔积。

python O(n) solution

class Solution: # @return a list of strings, [s1, s2] def letterCombinations(self, digits): # define a dictionary of the character <-> number projection pad = {'2':'abc', '3':'def', '4':'ghi', '5':'jkl', '6':'mno', '7':'pqrs', '8':'tuv', '9':'wxyz'} # if the input is empty if len(digits) == 0: return [""] # for number string length equals n-1 d0 = digits[:-1] comb0 = self.letterCombinations(d0) # combine the last digit with previous n-1 string d1 = digits[-1] string1 = pad[d1] comb1 = [] # consider every combinations for s in string1: for c in comb0: cs = c+s comb1.append(cs) return comb1

反思

先写出来，再优化