[leetcode 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'].

풀이:

- 매핑과 백트래킹 사용

class Solution {
public:
    vector<string> answer;
    string v[10];
    
    void BackTracking(string &digits, int idx, string result){
        if(idx == digits.length()){
            answer.push_back(result);
            return;
        }
        for(char s: v[digits[idx]-'0']){
            BackTracking(digits, idx+1, result + s);
        }
    }
    vector<string> letterCombinations(string digits) {
        
        if(digits.length()==0){
            return answer;
        }
        v[2]="abc";
        v[3]="def";
        v[4]="ghi";
        v[5]="jkl";
        v[6]="mno";
        v[7]="pqrs";
        v[8]="tuv";
        v[9]="wxyz";
        
        BackTracking(digits, 0, "");
        return answer;
    }
};