Accepted C++ recursion solution


  • 0
    W
    void getCombs(string digits, vector<string>& combs, unordered_map<int, string>& myMap)
    {
    	if (digits.empty()) return;
    	
    	char c = digits.at(0);
    	auto newStr = myMap.at(c - '0');
    	vector<string> combsCopy(combs);
    	
        // copy paste current combinations so {a, b} becomes {a, b, a, b, a, b} 
    	for (int i = 0; i < newStr.size() - 1; i++)
    		combs.insert(combs.end(), combsCopy.begin(), combsCopy.end());
    
        // {a, b, a, b, a, b} will become {aa, ba, ab, bb, ac, bc} when current digit is 2
    	int newStrIndex = 0;
    	for (int i = 0; i < combs.size(); i++)
    	{
    		if (i != 0 && i % combsCopy.size() == 0)
    			newStrIndex++;
    		char newC = newStr.at(newStrIndex);
    		combs.at(i) += newC;
    	}
    	
        // special case. can't append chars in the first recursion, so add them.
    	if (combs.empty())
    	{
    		for (int i = 0; i < newStr.size(); i++)
    		{
    			combs.push_back({newStr.at(i)});
    		}
    	}
    	
    	getCombs(digits.substr(1), combs, myMap);  // recurse with front digit removed
    }
    
    vector<string> letterCombinations(string digits)
    {
    	vector<string> combs;
    	if (digits.empty()) return combs;
    	
    	unordered_map<int, string> myMap;
    	myMap.insert(pair<int, string>(2, "abc"));
    	myMap.insert(pair<int, string>(3, "def"));
    	myMap.insert(pair<int, string>(4, "ghi"));
    	myMap.insert(pair<int, string>(5, "jkl"));
    	myMap.insert(pair<int, string>(6, "mno"));
    	myMap.insert(pair<int, string>(7, "pqrs"));
    	myMap.insert(pair<int, string>(8, "tuv"));
    	myMap.insert(pair<int, string>(9, "wxyz"));
    	
    	getCombs(digits, combs, myMap);
    	return combs;
    }

Log in to reply
 

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