[LeetCode] 17번 - Letter Combination of a Phone Number [Swift]

문제 링크

Letter Combinations of a Phone Number - LeetCode

문제

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

문제 풀이

이 문제는 그림으로 주어진 키보드를 사용하여 입력받은 번호로 만들 수 있는 모든 문자를 구하는 문제였습니다.

예제로 주어진 값으로 문제를 이해해보자면, "23"이 입력되었으면 2번, 3번 키보드로 만들 수 있는 모든 문자를 구하는 거예요.

 

근데 여기서 순서를 유지해야 합니다.

즉 "23"이 입력되었기 때문에 결과도 "(2번 키보드로 만들 수 있는 문자)(3번 키보드로 만들 수 있는 문자)" 이렇게 나와야 하는 것이죠~

이를 어떻게 만들 수 있느냐~ 하면 위의 그림을 보시면 방법을 알 수 있습니다.

모든 경우를 다 구해야 하기 때문에 앞 글자부터 하나씩 고정 해면서 모든 경우의 수를 구하면 되는데요, 이렇게 모든 경우를 구할 때 dfs를 사용하면 좋습니다.

dfs는 깊이 우선 탐색이므로 해당 깊이의 문자를 고정해두고 그 아래 깊이의 문자에서 나올 수 있는 모든 경우를 구합니다.

위와 그림과 같이 "234"가 주어졌다면 첫 번째 글자를 a로 고정하고 두 번째 글자를 d로 고정하고 세 번째 글자를 g로 고정하려고 하는데 세 번째 글자가 가장 깊은곳이기 때문에 adg를 추가하고 세번째 글자를 변경해주는 방식으로 dfs를 사용하시면 됩니다.

 

이렇게 하면 모든 경우의 문자를 구할 수 있었습니다!

소스 코드

class Solution {
    func letterCombinations(_ digits: String) -> [String] {
        let inputArray = digits.map({Int(String($0))!})
        
        let button: [Int: [String]] = [
            2: ["a","b","c"],
            3: ["d","e","f"],
            4: ["g","h","i"],
            5: ["j","k","l"],
            6: ["m","n","o"],
            7: ["p","q","r","s"],
            8: ["t","u","v"],
            9: ["w","x","y","z"]
        ]
        var result: [String] = []
        
        func dfs(_ temp: String, _ index: Int) {
            // 만약 글자길이가 처음 입력된 번호의 길이와 같으면 결과에 추가합니다.
            if index == inputArray.count {
                result.append(temp)
                return
            }
            
            for i in 0..<button[inputArray[index]]!.count {
                let next = temp + button[inputArray[index]]![i]
                dfs(next, index+1)
            }
        }
        
        if inputArray.count == 0 {
            return result
        } else if inputArray.count == 1 {
            result = button[inputArray[0]]!
            return result
        } else {
            for i in 0..<button[inputArray[0]]!.count {
                let temp: String = button[inputArray[0]]![i]
                dfs(temp,1)
            }
            return result
        }
    }
    
}