Letter Phone
Problem Statement : For a given phone number string, fetch all letter (A-Z) combinations that may be obtained.
Example : For a number 42, the possible combinations of letters (strings) that can be formed are
[ ga, gb, gc, ha, hb, hc, ia, ib, ic ].
Letter phone problem can be easily solved using the backtracking algorithm.
Consider the number 42; when the button 4 is pressed, the possible strings can begin with any of the letters [ g, h, i ].
We could start generating the strings with letter [ g ] first and then with [ h, i ]. When the button 2 is pressed, the possible letters [ a b c ] append to the previous letter [ g ]. This would generate strings [ ga, gb, gc ]. Every time a string is generated, we check its size. If the string size is the same as the length of the phone number, we backtrack to generate new string combinations.
Example of letter phone string generation backtracking algorithm for number 42.
| Number (42) Length | Number pressed | Generated String | Genrated String Size | Next Operation |
|---|---|---|---|---|
| 2 | 4 | g | 1 | Press Next Number |
| 2 | 2 | ga | 2 | Number length == Generated string size. Backtrack from [ a ] and append next letter [ b ] |
| 2 | 2 | gb | 2 | Number length == Generated string size. Backtrack from [ b ] and append next letter [ c ] |
| 2 | 2 | gc | 2 | Number length == Generated string size. Since there isn’t any letter left from number 2, backtrack from [ g ] and start with the next letter [ h ] |
| 2 | 4 | h | 1 | Append letter [ a ] |
| 2 | 2 | ha | 2 | Number length == Generated string size. Backtrack from [ a ] and append next letter [ b ] |
| 2 | 2 | hb | 2 | Number length == Generated string size. Backtrack from [ b ] and append next letter [ c ] |
| 2 | 2 | hc | 2 | Number length == Generated string size. Since there isn’t any letter left from number 2, backtrack from [ h ] and start with the next letter [ i ] |
| 2 | 4 | i | 1 | Append letter [ a ] |
| 2 | 2 | ia | 2 | Number length == Generated string size. Backtrack from [ a ] and append next letter [ b ] |
| 2 | 2 | ib | 2 | Number length == Generated string size. Backtrack from [ b ] and append next letter [ c ] |
| 2 | 2 | ic | 2 | Number length == Generated string size. Since there isn’t any letter left from number 2, backtrack from [ i ]. No more letters. Algorithm ends. |
Program for generating all possible strings on a letter phone.
class Phone :
def __init__ (self) :
self.num_to_char = { '0' : "0",
'1' : "1",
'2' : "abc",
'3' : "def",
'4' : "ghi",
'5' : "jkl",
'6' : "mno",
'7' : "pqrs",
'8' : "tuv",
'9' : "wxyz" }
self.possible_strings = []
def Generate (self, current_pressed, digit_str) :
if (len(current_pressed) == len(digit_str)) :
self.possible_strings.append(current_pressed)
else :
# Go through all the possible letter(s) in the current pressed number
for c in self.num_to_char[digit_str[len(current_pressed)]] :
current_pressed += c
self.Generate(current_pressed, digit_str)
current_pressed = current_pressed[:-1] # Remove the last appended character i.e backtrack
return self.possible_strings
def AllStrings (self, digit_str) :
self.possible_strings = []
current_pressed = ""
self.Generate(current_pressed, digit_str)
return self.possible_strings
def main() :
p = Phone()
print("Possible strings for code 22 : " + str(p.AllStrings("22")))
print("Possible strings for code 1232 : " + str(p.AllStrings("1232")))
print("Possible strings for code 1232 : " + str(p.AllStrings("42")))
if __name__ == "__main__" :
main()
Output
Possible strings for code 22 : ['aa', 'ab', 'ac', 'ba', 'bb', 'bc', 'ca', 'cb', 'cc']
Possible strings for code 1232 : ['1ada', '1adb', '1adc', '1aea', '1aeb', '1aec', '1afa', '1afb', '1afc', '1bda', '1bdb', '1bdc', '1bea', '1beb', '1bec', '1bfa', '1bfb', '1bfc', '1cda', '1cdb', '1cdc', '1cea', '1ceb', '1cec', '1cfa', '1cfb', '1cfc']
Possible strings for code 1232 : ['ga', 'gb', 'gc', 'ha', 'hb', 'hc', 'ia', 'ib', 'ic']
#include<iostream>
#include<map>
#include<vector>
using namespace std;
class Phone {
public :
map<char, string> num_to_char;
vector<string> possible_strings;
Phone() {
num_to_char['0'] = "0";
num_to_char['1'] = "1";
num_to_char['2'] = "abc";
num_to_char['3'] = "def";
num_to_char['4'] = "ghi";
num_to_char['5'] = "jkl";
num_to_char['6'] = "mno";
num_to_char['7'] = "pqrs";
num_to_char['8'] = "tuv";
num_to_char['9'] = "wxyz";
}
void Generate (string& current_pressed, string& digit_str) {
if (current_pressed.size() == digit_str.size()) {
possible_strings.push_back(current_pressed);
} else {
// Go through all the possible letter(s) in the current pressed number
for (const auto& ch : num_to_char[digit_str[current_pressed.size()]]) {
current_pressed.push_back(ch);
Generate(current_pressed, digit_str);
// Backtrack so that the next letter on the button can be used to form other strings.
current_pressed.pop_back();
}
}
}
vector<string> AllStrings (string digit_str) {
string current_pressed("");
possible_strings.clear();
Generate(current_pressed, digit_str);
return possible_strings;
}
};
int main() {
Phone p;
vector<string> numbers = {"22", "1232", "42"};
for (const auto& number : numbers) {
vector<string> possible_strings = p.AllStrings(number);
cout << "\n\nPossible strings for code " << number << " : ";
for (const auto& str : possible_strings)
cout << str << " ";
}
return 0;
}
Output
Possible strings for code 22 : aa ab ac ba bb bc ca cb cc
Possible strings for code 1232 : 1ada 1adb 1adc 1aea 1aeb 1aec 1afa 1afb 1afc 1bda 1bdb 1bdc 1bea 1beb 1bec 1bfa 1bfb 1bfc 1cda 1cdb 1cdc 1cea 1ceb 1cec 1cfa 1cfb 1cfc
Possible strings for code 42 : ga gb gc ha hb hc ia ib ic
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;
class Phone {
public HashMap<Character, String> num_letters;
public List<String> possible_strings;
Phone() {
num_letters = new HashMap<Character, String>();
num_letters.put('0', "0");
num_letters.put('1', "1");
num_letters.put('2', "abc");
num_letters.put('3', "def");
num_letters.put('4', "ghi");
num_letters.put('5', "jkl");
num_letters.put('6', "mno");
num_letters.put('7', "pqrs");
num_letters.put('8', "tuv");
num_letters.put('9', "wxyz");
possible_strings = new ArrayList<String>();
}
public void Generate (String current_pressed, String digit_str) {
if (current_pressed.length() == digit_str.length()) {
possible_strings.add(current_pressed);
} else {
// Go through all the possible letter(s) in the current pressed number
String letters = num_letters.get(digit_str.charAt(current_pressed.length()));
for (int i=0; i < letters.length(); i++) {
current_pressed += letters.charAt(i);
Generate(current_pressed, digit_str);
// Backtrack so that the next letter on the button can be used to form other strings.
current_pressed = current_pressed.substring(0, current_pressed.length() - 1);
}
}
}
List<String> AllStrings (String digit_str) {
String current_pressed = new String("");
possible_strings.clear();
Generate(current_pressed, digit_str);
return possible_strings;
}
public static void main (String[] args) {
Phone p = new Phone();
String[] numbers = new String[] {"22", "1232", "42"};
for (String number: numbers) {
List<String> possible_strings = p.AllStrings(number);
System.out.println( "\n\nPossible strings for number : " + number);
for (String str : possible_strings)
System.out.print(str + " ");
}
}
}
Output
Possible strings for number : 22
aa ab ac ba bb bc ca cb cc
Possible strings for number : 1232
1ada 1adb 1adc 1aea 1aeb 1aec 1afa 1afb 1afc 1bda 1bdb 1bdc 1bea 1beb 1bec 1bfa 1bfb 1bfc 1cda 1cdb 1cdc 1cea 1ceb 1cec 1cfa 1cfb 1cfc
Possible strings for number : 42
ga gb gc ha hb hc ia ib ic