LeedCode : 17. Letter Combinations of a Phone Number

오랜만에 dfs문제를 풀고 싶어서 LeetCode에서 dfs태그로 들어갔다.

재밌는 문제가 많아보였지만 역시 첫 번째 문제부터 들어갔다.

 

간단하게 dfs 재귀 방식으로 풀 수 있었다.

 

[메인 로직]

vector에 2~9까지의 idx에 각각 해당되는 문자를 넣어주었고

dfs로 digits에 해당되는 문자를 하나씩 탐색했다.

 

class Solution {
public:
    vector<string> ans;
    vector<char> phone[11];
    
    void dfs(string digits, int idx, string temp){        
        if(idx==digits.size()){
            ans.push_back(temp);
            return;
        }
        
        for(int i=0; i<phone[digits[idx]-'0'].size(); i++){
            dfs(digits, idx+1, temp+phone[digits[idx]-'0'][i]);
        }
    }
    
    vector<string> letterCombinations(string digits) {
        if(digits==""){
            return ans;
        }
        
        int idx = 0;
        
        for(int i=2; i<=9; i++){
            if(i==7 || i==9){ // 4개
                for(int j=0; j<4; j++){
                    char c = idx+'a';
                    phone[i].push_back(c);
                    idx++;
                }
            }else{ // 3개
                for(int j=0; j<3; j++){
                    char c = idx+'a';
                    phone[i].push_back(c);
                    idx++;
                }
            }
        }
        
        dfs(digits, 0, "");
        
        return ans;
    }
};