Letter Phone

Letter Phone

Problem Statement : For a given number, 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 4 is pressed, the possible strings can begin with [ g, h, i ]. String generation can start with the letter ‘g’ followed by ‘h’ and ‘i’. When 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 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.

Python

Python : Generating all possible strings on a letter phone. Implemented in Python 3.8


C++ : Generating all possible strings on a letter phone. Implemented in C++11

#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);
                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> possible_strings_1 = p.AllStrings("22");
    cout << "Possible strings for code 22 : ";
    for(const auto& str : possible_strings_1)
        cout << str << " ";

    cout << "\nPossible strings for code 1232 : ";
    vector<string> possible_strings_2 = p.AllStrings("1232");
    for(const auto& str : possible_strings_2)
        cout << str << " ";

    vector<string> possible_strings_3 = p.AllStrings("42");
    cout << "<nPossible strings for code 42 : ";
    for(const auto& str : possible_strings_3)
        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

Copyright (c) 2020, Algotree.org.
All rights reserved.