[Leetcode][17] Letter Combinations of a Phone Number

문제 : leetcode.com/problems/letter-combinations-of-a-phone-number/

---

전화 버튼과 동일한 숫자와 문자의 매핑이 있다.

2~9까지의 숫자로 이루어진 문자열이 주어지면 가능한 모든 문자 조합을 반환해라.

---

하나의 숫자에 복수개의 문자가 매핑되므로 dict[숫자] = 문자의 배열 을 먼저 구해준다.

가능한 문자 조합들은 백트래킹을 이용하여 구한다.

 

예시로 주어진 23이면

1. 빈 문자열부터 시작해서 2에 해당하는 문자들 중 하나를 넣고("a") 다음 숫자를 판단한다. 

2. "a" 이후 3에 해당하는 문자들 중 하나를 세팅한다. "ad". 모든 digits들의 숫자를 판단했으므로 "ad"를 정답에 추가한다.

3. 가장 마지막 문자를 제거한 후('d'가 제거되어 "a"만 남는다.) digits 중 바로전에 탐색한 숫자를 다시 탐색한다. 이전에 세팅하지 않았던 문자들 중 하나를 추가한다. "ae". 모든 digits 숫자를 판단했으므로 "ae"를 정답에 추가한다.

4. 3와 마찬가지로 마지막 문자 제거 후 세팅하지 않았던 문자를 추가한다. "af". 모든 digits 숫자를 판단했으므로 "af"를 정답에 추가한다.

5. 마지막 문자 제거 후 ("a") 세팅하지 않았던 문자를 추가해야 하는데 이미 3 에 해당하는 모든 문자들을 탐색하였다. 따라서 숫자 2에 해당하는 문자를 제거한 후("") 2에 해당하는 문자들 중 탐색하지 않은 문자를 세팅한다. "b"

6. 2~5 를 반복한다.

 

시간복잡도는 digits 길이를 N이라 하였을 때, 숫자 7, 9에 해당하는 문자들의 수가 4이므로 O(4^N)이 된다.

---

소스코드 : github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/17.%20Letter%20Combinations%20of%20a%20Phone%20Number.cpp