Leetcode/LeetCode75

[Backtracking][Medium] 17. Letter Combinations of a Phone Number

자전거통학 2024. 1. 13. 00:21

https://leetcode.com/problems/letter-combinations-of-a-phone-number/description

 

Letter Combinations of a Phone Number - LeetCode

Can you solve this real interview question? Letter Combinations of a Phone Number - Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of d

leetcode.com

 

Q. 입력된 string digits에 아래와 같은 숫자패드를 입력 할 수 있다. 

 이 때 출력 가능한 모든 문자 조합을 출력하라. 

 

 

Solution. 

 Backtracking의 고전과도 같은 문제. 

 

 backtracking의 로직을 그대로 적용하면 된다. 

 이와는 별개로 backtracking은 실생활의 문제를 푸는데 많은 도움이 될수 있다. 

 흥미를 가지고 봐야 할 항목.

 

 void letter_helper(map<char, string>& mapData, string digits, string curStr, vector<string>& vOut)
{
    if (curStr.size() == digits.size())
    {
        if(digits.size() > 0)	// check only valid string set.
            vOut.push_back(curStr);
        return;
    }

    int idx = curStr.size();
    string strTarget = mapData[digits.at(idx)];
    for (int k = 0; k < strTarget.size(); ++k)
    {
        curStr += strTarget[k];        // push in 
        letter_helper(mapData, digits, curStr, vOut);
        curStr.erase(curStr.end()-1);  // pop out
    }
}

vector<string> letterCombinations(string digits) 
{
    // Build Local data for the key pad.
    map<char, string> mapData;
    mapData['2'] = "abc";
    mapData['3'] = "def";
    mapData['4'] = "ghi";
    mapData['5'] = "jkl";
    mapData['6'] = "mno";
    mapData['7'] = "pqrs";
    mapData['8'] = "tuv";
    mapData['9'] = "wxyz";

    vector<string> vOut;
    letter_helper(mapData, digits, "", vOut);
    return vOut;
}

 

 

작은 속도안에서의 순위차는 무시한다.