LeetCode [17] Letter Combinations of a Phone Number

 17. Letter Combinations of a Phone Number

Medium

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Example 1:

Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

 

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

class Solution { Map<Character, char[]> map = new HashMap<>(); List<String> ret = new ArrayList<>(); public List<String> letterCombinations(String digits) { map.put('2', new char[]{'a','b','c'}); map.put('3', new char[]{'d','e','f'}); map.put('4', new char[]{'g','h','i'}); map.put('5', new char[]{'j','k','l'}); map.put('6', new char[]{'m','n','o'}); map.put('7', new char[]{'p','q','r','s'}); map.put('8', new char[]{'t','u','v'}); map.put('9', new char[]{'w','x','y','z'}); dfs(digits, 0, ""); return ret; } void dfs(String digits, int i, String str){ if(i==digits.length()){ if(str.length()>0) ret.add(str.toString()); }else{ char d = digits.charAt(i); for(char c : map.get(d)){ dfs(digits, i+1, str+c); } } } }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

//c++ class Solution { string phone[10]; public: Solution(){ phone[2] = "abc"; phone[3] = "def"; phone[4] = "ghi"; phone[5] = "jkl"; phone[6] = "mno"; phone[7] = "pqrs"; phone[8] = "tuv"; phone[9] = "wxyz"; } vector<string> letterCombinations(string digits) { vector<string> res; if(digits=="") return res; bt(digits, 0, res, "", digits.size()); return res; } void bt(string digits, int pos, vector<string> &res, string cur, int nd){ if(pos==nd){ res.push_back(cur); }else{ int d = digits[pos]-'0'; for(int i=0; i<(int)phone[d].size(); ++i){ string s = cur; s.append(1, phone[d][i]); bt(digits, pos+1, res, s, nd); } } } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

//c++ class Solution { unordered_map<int, string> hash; public: Solution(){ hash[2] = "abc"; hash[3] = "def"; hash[4] = "ghi"; hash[5] = "jkl"; hash[6] = "mno"; hash[7] = "pqrs"; hash[8] = "tuv"; hash[9] = "wxyz"; } string plus1(string cnt, string s){ int carry = 1, n = s.size(); string ret; for(int i=n-1; i>=0; --i){ int d = s[i]-'0'; int w = hash[d].size(); int sum = (cnt[i]-'0')+carry; carry = sum/w; ret += char(sum%w+'0'); } if(carry) ret += char(carry+'0'); reverse(ret.begin(), ret.end()); return ret; } vector<string> letterCombinations(string digits) { vector<string> ret; int n = digits.size(); if(n==0) return ret; string cnt(n, '0'); while(cnt.size()<=n){ string s; for(int i=0; i<n; ++i){ int d = digits[i]-'0'; int index = cnt[i]-'0'; s += hash[d][index]; } ret.push_back(s); cnt = plus1(cnt, digits); } return ret; } };