Letter Combinations of a Phone Number


  • 0
    S

    class Solution {
    public:
    unordered_map<char,string> HashMap = { {'1',""}, {'2', "abc"},{'3', "def"},{'4', "ghi"},{'5', "jkl"},
    {'6',"mno"},{'7',"pqrs"},{'8',"tuv"},{'9',"wxyz"},{'0',""}};

    void letterletterCombinationsHelper(string &d, int digit,string partial,vector<string> &v){
     
        if(partial.size() == d.size())
        {
            v.emplace_back(partial);
        }
        else{
        for (const char &c: HashMap[d[digit]]){
            letterletterCombinationsHelper(d,digit+1,partial+c,v);
          }
              
        }
    }
    
    vector<string> letterCombinations(string digits) {
        vector<string> s; 
        string partial;
        if(digits == ""){
            return {};
        }
        letterletterCombinationsHelper(digits,0,partial,s);
        return s;
    }
    

    };


  • 0
    D
    class Solution {
    public:
        vector<string> letterCombinations(string digits) 
        {
            static const vector<vector<char>> v_map
                                      {
                                       {}, 
                                       {}, 
                                       {'a', 'b', 'c'},
                                       {'d', 'e', 'f'},
                                       {'g', 'h', 'i'},
                                       {'j', 'k', 'l'},
                                       {'m', 'n', 'o'},
                                       {'p', 'q', 'r', 's'},
                                       {'t', 'u', 'v'},
                                       {'w', 'x', 'y', 'z'}
                                      };
            vector<string> rt;
            auto len = digits.length();
            if (0 == len)
                return rt;
            for (std::size_t i = 0; i < digits.size(); ++i)
            {
                const auto& v = v_map[digits[i] - '0'];
                if (rt.empty())
                {
                    for (std::size_t j = 0; j < v.size(); ++j)
                    {
                        string str = "";
                        str += v[j];
                        rt.push_back(str);
                    }
                }
                else
                {
                    if (!v.empty())
                    {
                        auto ori_size = rt.size();
                        for (std::size_t j = 1; j < v.size(); ++j)
                        {
                            for (std::size_t k = 0; k < ori_size; ++k)
                            {
                                rt.push_back(rt[k] + v[j]);
                            }
                        }
                        for (std::size_t k = 0; k < ori_size; ++k)
                        {
                            rt[k] += v[0];
                        }
                    }
                }
            }
            return rt;
        }
    };
    

  • 0
    H

    Here is an iterative solution using a dictionary to store phone number values:
    """
    class Solution:
    def letterCombinations(self, digits):

        phoneNumbers = {"1":"","2":"abc","3":"def","4":"ghi","5":"jkl","6":"mno","7":"pqrs","8":"tuv","9":"wxyz","0":""}
        newArray = []
        isFirstDigit = True
    
        if(len(digits) == 0):
            return newArray
        
        for i in digits:
            prevIndex = 0
            tempString = phoneNumbers[i]
            tempArray = newArray[:]  
            for z in range(0,len(phoneNumbers[i])):
                tempString = phoneNumbers[i]
                if(isFirstDigit):
                    newArray.append(tempString[z])
                    tempArray = newArray[:]
                    
                elif(tempString != ""):
                    if(z != 0 & z < len(phoneNumbers[i])):
                        newArray.extend(tempArray)    
                    print prevIndex, " - ", len(newArray), " - ", len(tempArray)
                    for k in range(prevIndex,len(newArray)):
                        #print newArray[k]
                        newArray[k] += tempString[z] 
                    prevIndex = len(newArray)
            isFirstDigit = False
            print len(newArray)
        return newArray
    

    """


  • 0
    A

    Another solution that use recursion

    class Solution {
    public:
        vector<string> letterCombinations(string digits) {
            vector<string> map(10);
            map[0] = "";
            map[1] = "";
            map[2] = "abc";
            map[3] = "def";
            map[4] = "ghi";
            map[5] = "jkl";
            map[6] = "mno";
            map[7] = "pqrs";
            map[8] = "tuv";
            map[9] = "wxyz";
            vector<string> result;
            if(digits.empty())
                return result;
            helper(digits, map, result, "");
            return result;
        }
    private:
        void helper(string digit, const vector<string>& map, vector<string>& result, string current) {
            if(digit.empty()) {
                result.push_back(current);
            } else {
                char curr = digit[0];
                digit = digit.substr(1);
                for(int i = 0; i < map[curr - '0'].size(); i++) {
                    helper(digit, map, result, current + map[curr - '0'][i]);
                }
            }
        }
    };
    

  • 0
    N

    class Solution {
    public:
    List<String> letterCombinations(String letter) {
    Map<String, String> numberToLetterMap = new HashMap<>();
    numberToLetterMap.put("1", null);
    numberToLetterMap.put("2", "abc");
    numberToLetterMap.put("3", "def");
    numberToLetterMap.put("4", "ghi");
    numberToLetterMap.put("5", "jkl");
    numberToLetterMap.put("6", "mno");
    numberToLetterMap.put("7", "pqrs");
    numberToLetterMap.put("8", "tuv");
    numberToLetterMap.put("9", "wxyz");
    int totalCombinations = 1;

        if (letter.length() == 0) {
            return new ArrayList();
        }
    
        for (int i = 0; i < letter.length(); i++) {
            if (letter.substring(i, i + 1).equalsIgnoreCase("1")) {
                return new ArrayList();
            }
            totalCombinations = totalCombinations * numberToLetterMap.get(letter.substring(i, i + 1)).length();
        }
        String wordsArray[] = new String[totalCombinations];
        int previousLetterCombinationLength = 0;
        if (totalCombinations > 0) {
            for (int i = letter.length() - 1; i >= 0; i--) {
                String alphabets = numberToLetterMap.get(letter.substring(i, i + 1));
                int wordsArrayLength = 0;
                String wordsArrayTemp[] = new String[previousLetterCombinationLength];
                for (int k = 0; k < previousLetterCombinationLength; k++) {
                    String tempVal = new String(wordsArray[k]);
                    wordsArrayTemp[k] = tempVal;
                }
                for (int j = 0; j < alphabets.length(); j++) {
                    String newAlphabet = alphabets.substring(j, j + 1);
                    if (i == letter.length() - 1) {
                        wordsArray[wordsArrayLength++] = newAlphabet;
                    } else {
                        for (int k = 0; k < previousLetterCombinationLength; k++) {
                            wordsArray[wordsArrayLength++] = newAlphabet + wordsArrayTemp[k];
                        }
                    }
                }
                previousLetterCombinationLength = wordsArrayLength;
            }
        }
        return Arrays.asList(wordsArray);
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.