[C++] LeetCode : Letter Combinations of a Phone Number

Question

2-9까지의 숫자가 포함된 string이 주어졌을 때, 해당 숫자로 나타낼 수 있는 모든 가능한 letter들을 return 하라. 단, 조합 가능한 letter들은 어떤 순서로 return 해도 상관없으며, 1은 어떤 letters로 mapping 되지 않는다. 

 

 

각 숫자판에서 입력가능한 문자들 (출처 - LeetCode)

제약사항

• string의 길이는 0 이상 4이하 이다.
• digits [i]의 범위는 ['2' , '9']이다.
  
  

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

  한 숫자당 입력 가능한 문자의 개수를 n, string의 최대 길이를 s 라 했을 때 BCR은 O(n^s)이다. 

고려사항

1. string의 길이가 0일 경우 
2. 잘못된 입력이 주어질 경우

Solution1 - Bruth Force , Recursive, Back Tracking

  가능한 모든 경우의 수를 고려해야 하기 때문에, 재귀적으로 모든 가능한 경우의 수를 탐색한다.

class Solution {
public:
    void make_permutation(string digits, string s, vector<string> chars, int point, vector<string>& ans) {
        if (point == digits.size()) {
            if(s != "") ans.push_back(s);
            return;
        }

        int d = digits[point] - '2';
        for (char ch : chars[d]) {
            make_permutation(digits, s + ch, chars, point + 1, ans);
        }

    }
    vector<string> letterCombinations(string digits) {
        vector<string> ans;
        const vector<string> chars = { "abc", "def", "ghi","jkl", "mno","pqrs","tuv","wxyz"};

        make_permutation(digits, "", chars, 0, ans);

        return ans;
    }
};

• Time complexity : O(4^s*s) //  한 숫자당 입력 가능한 문자의 개수가 최대 4, string의 최대 길이를 s 라 했을 때 O(4^s)이고 문자를 이어 붙이는데 O(s)의 시간이 소요됨으로 O(4^s*s)이다.
• Space Complexity : O(s) // s을 입력된 문자열의 최대 길이라 했을 때 recursion은 최대 s만큼 발생하므로, O(s)이다.

 

출처 : https://leetcode.com/explore/interview/card/top-interview-questions-medium/109/backtracking/793/

Explore - LeetCode

* 본 포스트 관련된 토의, 지적 및 조언은 모두 환영합니다