[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.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

 

풀이

재귀함수를 이용하여 구한다.

string $s$에서 맨 앞 글자를 빼고 구성한 string을 $s'$이라고 하면

$letterCombinations(s)$ = (맨 앞글자 한 글자에 해당하는 글자 리스트) $\prod letterCombinations(s')$ 

이므로, 이 관계를 이용하여 함수를 구현한다.

 

Time Complexity : $O(4^|S|)$

 

코드

class Solution {
private:
    vector<string> let[10]={{},{},{"a","b","c"},{"d","e","f"},
                           {"g","h","i"},{"j","k","l"},
                           {"m","n","o"},{"p","q","r","s"},
                           {"t","u","v"},{"w","x","y","z"}};
public:
    vector<string> letterCombinations(string digits) {
        if(digits=="") return vector<string>();
        
        vector<string> ret(0);
        int num = digits[0]-'0';
        if(digits.length()==1)return let[num];
        
        vector<string> s=letterCombinations(digits.substr(1));
        for(int i=0;i<let[num].size();i++)
            for(int j=0;j<s.size();j++)
                ret.push_back(let[num][i]+s[j]);
        return ret;
    }
};