[LeetCode, 리트코드] Letter Combinations of a Phone Number

 

1. Problem

 

2-9의 숫자로 이루어진 문자열이 주어질 때, 숫자가 표현할 수 있는 모든 가능한 문자 조합을 구하여라. 각 숫자가 나타낼 수 있는 문자의 리스트는 아래 그림과 같다. 1은 어떤 문자도 나타낼 수 없다.

 

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

2. Solution

 

간단한 순회 문제다. 하지만 중요한 부분은 digits의 수가 얼마나 올지 알 수 없으므로 단순 for문을 돌리면 처리가 매우 어렵다는 사실이다.

 

DFS로 돌려서 각 조합들을 찾아내면 어렵지 않게 찾아낼 수 있다.

 

3. Code

class Solution {
    vector<string> ret;
    vector<string> numToLetters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<int> digitNumbers;
public:
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0)
            return vector<string>();
        ret.clear();
        digitNumbers.clear();
        
        for(int i=0; i<digits.size(); ++i){
            digitNumbers.push_back(digits[i] - '0');
        }
        
        for(int i=0; i< numToLetters[digitNumbers[0]].size(); ++i){
            int digit = digitNumbers[0];
            string s(1, numToLetters[digit][i]);
            getAllPossibleCombination(1, s);
        }
        
        return ret;
    }
    
    void getAllPossibleCombination(int idx, string s){
        //cout << s << endl;
        if(idx >= digitNumbers.size()){
            ret.push_back(s);
            return;
        }
    
        int digit = digitNumbers[idx];
        string letters = numToLetters[digit];
        for(int i=0; i<letters.size(); ++i){
            getAllPossibleCombination(idx+1, s + letters[i]);
        }
        
        return;
    }
};