(Leet Code c++)Letter Combinations of a Phone Number

17. 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 digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

Example 1:

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

Example 2:

Input: digits = "" Output: []

Example 3:

Input: digits = "2" Output: ["a","b","c"]

 

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

DFS를 통해 문제 해결.

 

주어진 문자열 digits가 비어있지 않으면 dfs()를 실행한다.

dfs()는 차례대로 현재까지 저장된 문자열, digits, 현재까지 진행한 인덱스를 넣어준다.

 

dfs()

number는 digits[n]이 가리키는 숫자의 int형이다.

 

만약 digits.size() - 1과 n이 같다면 종료조건에 해당한다.

for문을 통해 str[number]에 해당하는 문자열의 길이만큼 반복.

현재까지 진행한 문자열 s와 str[number]가 가리키는 문자를 합쳐서 answer에 넣어 준 후 리턴한다.

 

종료조건에 해당하지 않는다면 문자를 number에 해당하는 문자를 합쳐서 계속 dfs를 실행한다.

class Solution {
public:
    string str[10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> answer;
    
    void dfs(string s, string digits, int n){
        int number = digits[n] - '0';
        
        if(digits.size() - 1 == n){
            for(int i = 0; i < str[number].size(); i++){
                answer.push_back(s + str[number][i]);
            }
            return;
        }
        
        for(int i = 0; i < str[number].size(); i++){
            string tmp = s + str[number][i];
            
            dfs(tmp, digits, n + 1);
        }
    }
    
    vector<string> letterCombinations(string digits) {
        vector<int> numbers;
        
        if(digits != ""){
            dfs("", digits, 0);
        }
        
        return answer;
    }
};