Coders Packet

Phone Number Combinations Using C++

By Savala Lingesh Reddy

Given a string containing digits from 2-9, print all possible letter combinations that the number could represent. Write code to achieve this using C++.

class Solution {
private:
    void recur(string s,unordered_map<char,string> &ump,
               vector &ans,string str,int u){
        if(s.size() == 0 && str.size() == u){
            ans.push_back(str);
            return;
        }
        for(int i=0;i<s.size();i++){
            string t = ump[s[i]];
            for(int j=0;j<t.size();j++){
                str.push_back(t[j]);
                recur(s.substr(i+1,s.size()-1),ump,ans,
str,u);
                str.pop_back();
            }
        }
    }
public:
    vector letterCombinations(string digits) {
        unordered_map<char,string> ump;
        ump['2'] = "abc";ump['3']="def";ump['4']="ghi";
        ump['5']="jkl";
        ump['6']="mno";ump['7']="pqrs";ump['8']="tuv";
        ump['9']="wxyz";
        vector ans;
        string str;int u = digits.size();
        if(u == 0)
            return ans;
        recur(digits,ump,ans,str,u);
        return ans;
    }
};

 

Here in this problem, we need to print all the combinations that can be obtained by solving the given string. 

Example: s = "23"

output : ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Approach: Map all the letters with digits as per the telephone buttons. Think in a recursive manner to solve the problem using depth-first search.

First, explore the 0 indexed digits and then the next digits. Use two for loops to achieve this. Outer for loop to traverse through the given string and inner loop to achieve the pattern.

 

 

Download project

Reviews Report

Submitted by Savala Lingesh Reddy (Lingesh)

Download packets of source code on Coders Packet