0ms recursive solution. What do you think?


  • 0
    K
    /*
     * begin.cpp
     *
     *  Created on: Mar 11, 2015
     *      Author: nightfall
     */
    #include<iostream>
    #include<vector>
    
    using namespace std;
    
    vector<string> letterCombinations(string digits);
    string getLetters(char digit);
    void rec(string digits, string toAppend, vector<string> &combinations);
    
    int main() {
    	vector<string> combinations = letterCombinations("23");
    	for (unsigned int i = 0; i < combinations.size(); i++) {
    		cout << combinations[i] << endl;
    	}
    	return 0;
    }
    
    vector<string> letterCombinations(string digits) {
    	vector<string> combinations;
    	rec(digits, "", combinations);
    	return combinations;
    }
    
    string getLetters(char digit) {
    	string result;
    	switch (digit) {
    		case '2':
    			result = "abc";
    			break;
    		case '3':
    			result = "def";
    			break;
    		case '4':
    			result = "ghi";
    			break;
    		case '5':
    			result = "jkl";
    			break;
    		case '6':
    			result = "mno";
    			break;
    		case '7':
    			result = "pqrs";
    			break;
    		case '8':
    			result = "tuv";
    			break;
    		case '9':
    			result = "wxyz";
    			break;
    		default:
    			result = "";
    			break;
    	}
    	return result;
    }
    
    void rec(string digits, string toAppend, vector<string> &combinations) {
    	if (digits.length() == 0) {
    		if (toAppend.length() != 0)
    			combinations.push_back(toAppend);
    	} else {
    		char lastDigit = digits[digits.length() - 1];
    		string letters = getLetters(lastDigit);
    		string temp = "";
    
    		for (unsigned int i = 0; i < (digits.length() - 1); i++)
    			temp += digits[i];
    
    		for (unsigned int i = 0; i < letters.length(); i++) {
    			string newAppend;
    			newAppend = letters[i] + toAppend;
    			rec(temp, newAppend, combinations);
    		}
    	}
    }
    

    I'm bad at explaining my thought process (working on it) but here goes...
    The idea here is to take all the possible letter combinations of the last digit and append each letter to all the possible letter combinations of the preceeding digit.


Log in to reply
 

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