3

(Letter Combinations of a Phone Number) | Runhe Tian Coding Practice

 2 years ago
source link: https://tianrunhe.wordpress.com/2012/07/27/letter-combinations-of-a-phone-number/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

(Letter Combinations of a Phone Number)

27 Jul 2012 2 Comments

by Runhe Tian in LeetCode Tags: C++, Java, Recursion, String

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.
200px-Telephone-keypad2.svg.png
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.

Thoughts:
Another classic recursion problem. We try to generate solution each time by iterating through every digit and every character that digit maps to. If we overflow, we cut that solution and stop. If we get the correct solution (where solution.length() == digits.length()), we add to the solution set.

Code (Java):

public class Solution {
private HashMap<Character, String> map;
public ArrayList<String> letterCombinations(String digits) {
setup();
ArrayList<String> solutions
= new ArrayList<String>();
recursion(digits, 0, new String(), solutions);
return solutions;
}
private void recursion(String digits, int start,
String sol, ArrayList<String> solutions) {
if(sol.length() > digits.length()) {
return; 
} else if(sol.length() == digits.length()) {
solutions.add(sol);
return;
} else {
for(int i = start; i < digits.length(); ++i) {
String letters = map.get(digits.charAt(i));
for(int j = 0; j < letters.length(); ++j) {
recursion(digits, i + 1, sol + letters.charAt(j), solutions);
}
}
}
}
private void setup() {
map = new HashMap<Character, String>();
map.put('1', "");
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");
map.put('0', " ");
}
}

Code (C++):

class Solution {
public:
vector<string> letterCombinations(string digits) {
setup();
vector<string> solutions;
string s;
recursion(digits, 0, s, solutions);
return solutions;
}
private:
map<char, string> mapping;
void recursion(string digits, int start,
string sol, vector<string>& solutions) {
if(sol.size() > digits.size()) {
return; 
} else if(sol.size() == digits.size()) {
solutions.push_back(sol);
return;
} else {
for(int i = start; i < digits.size(); ++i) {
string letters = mapping[digits[i]];
for(int j = 0; j < letters.size(); ++j) {
recursion(digits, i + 1, sol + letters[j], solutions);
}
}
}
}
void setup() {
mapping.clear();
mapping['1'] = "";
mapping['2'] = "abc";
mapping['3'] = "def";
mapping['4'] = "ghi";
mapping['5'] = "jkl";
mapping['6'] = "mno";
mapping['7'] = "pqrs";
mapping['8'] = "tuv";
mapping['9'] = "wxyz";
mapping['0'] = " ";
}
};

Previous (Length of Last Word) Next Find the longest common prefix in an array of strings (Longest Common Prefix)

2 Comments (+add yours?)

  1. b4763bab880850baecfcd6e661527cac?s=48&d=identicon&r=GNader
    Oct 21, 2012 @ 12:07:19

    The following loop is not necessary:
    for(int i = start; i < digits.size(); ++i) { […] }
    Even though it does return the correct result. See the following link for a variation of the code above without the loop: http://pastebin.com/qJc5nSvE
    Regards. And thanks again for this awesome blog.

    Reply

  2. d6b30d1867b4dad4d71b2ec7657612ea?s=48&d=identicon&r=GNankai
    Jan 26, 2013 @ 17:32:23

    The program is not correct if you have this loop:
    for(int i = start; i < digits.size(); ++i) { […] }

    Reply

Leave a Reply Cancel reply


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK