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

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

 

2-9 까지의 다이얼을 누른다고 할 때, 매칭 가든한 모든 문자열을 찾아라.

 

BackTracking의 고전과도 같은 문제. 

depth가 더해 지면서 진행 하는 index 는 찾고자 하는 input digit이다. 

이 데이터를 가지고 가질 수 있는 문자를 문자열의 길이가 digits만큼 되면 반환 buff에 넣는다. 

 

코드 

void letterCombinationsBT(const string& digits, map<char, vector<char>>& buff, vector<string>& vOut, string& cur)
{
    if (cur.size() >= digits.size())
    {
        if(cur.size() > 0)
            vOut.push_back(cur);
        return;
    }

    char num = digits[cur.size()];
    auto vChar = buff[num];
    for (int q = 0; q < vChar.size(); ++q)
    {
        cur.push_back(vChar[q]);
        letterCombinationsBT(digits, buff, vOut, cur);
        cur.pop_back();
    }
}

vector<string> letterCombinations(string digits) 
{
    map<char, vector<char>> buff;
    buff['2'] = { 'a', 'b', 'c' };
    buff['3'] = { 'd', 'e', 'f' };
    buff['4'] = { 'g', 'h', 'i' };
    buff['5'] = { 'j', 'k', 'l' };
    buff['6'] = { 'm', 'n', 'o' };
    buff['7'] = { 'p', 'q', 'r', 's'};
    buff['8'] = { 't', 'u', 'v' };
    buff['9'] = { 'w', 'x', 'y', 'z'};

    vector<string> vOut;
    string cur;
    letterCombinationsBT(digits, buff, vOut, cur);
    return vOut;
}

 

 

결과