(LeetCode) 17. Letter Combinations of a Phone Number

The link : leetcode.com/problems/letter-combinations-of-a-phone-number/

Letter Combinations of a Phone Number - LeetCode

문제는 다음과 같다. 

1.

사진과 같은 전화기가 주어지며, 2번~9번 사이의 수가 최대 길이 4를 넘지 않을만큼 주어진다. 

단, 주어지는 값은 문자열이다.

2. 다이얼 패드로 가능한 조합들을 출력하라. 예시는 다음과 같다.

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

---

문제의 키포인트는 다음과 같았다.

 

1. 문자를 지우기 위해서 'erase' 사용

2. 문자를 숫자로 전환하기 위해 아스키코드 계산식을 활용 (문자형 - 48 = 숫자형)

class Solution {

    string phone[10] = { "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" };
    vector<string> ans;

public:
    vector<string> letterCombinations(string digits) {
        string res = "";
        if (digits != "") dfs(digits, 0, res);
        return ans;
    }
    void dfs(string s1, int cnt, string s2) {
        if (s1.size() == cnt) {
            ans.push_back(s2);
            return;
        }
        for (int i = cnt; i < s1.size();i++) {
            for (int j = 0; j < phone[s1[i] - 48].size(); j++) {
                s2 += phone[s1[i] - 48][j];
                dfs(s1, cnt + 1, s2);
                s2.erase(s2.size() - 1, 1); // 글자를 지우려는 위치, 해당 위치부터 지우는 글자 갯수
            }
            break; // 중요
        }
    }
};

핵심 포인트는 다이얼패드 하나 당 하나의 값만을 추가해야한다는 점이다. 

2중 for문 사이에 break를 설정하지 않을 경우, 다이얼패드를 계속해서 넘겨버려

결국 패드 하나당 단어 하나만을 누적시키는 것이 불가능해진다.