[LeetCode] 17. Letter Combinations of a Phone Number (C++)

문제

위의 사진의 2부터 9 숫자 버튼에 문자가 포함되어 있다.

중복되지 않는 모든 가능한 문자열을 찾기

생각할 것

입력으로 들어온 숫자 하나에 대해 모든 문자를 하나씩 대입해야 할 것이다!

반례

빈 digits로 시작했을 때 빈 문자열을 배열에 추가하는 문제

input : digits = ""
output : [""]
expected : []

유효하지 않은 결과이므로 배열에 추가하면 안된다!

if(strs.size() > 0) 인 경우에만 문자열을 결과배열에 추가하도록 수정했다.

코드

class Solution {
public:
    vector<string> res; 
    vector<string> m = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    string strs = "";

    void dfs(int idx, string digits){
        if(idx == digits.size()){
            if(strs.size() > 0) res.push_back(strs);           
            return;    
        }

        for(int i=0; i<m[digits[idx] - '0'].size(); i++){
            strs.push_back(m[digits[idx] - '0'][i]);
            dfs(idx+1, digits);
            strs.pop_back();
        }   
    }

    vector<string> letterCombinations(string digits) {   
        dfs(0, digits);
        return res;
    }
};