BackTrack.swift

class Solution {
     func letterCombinations(_ digits: String) -> [String] {
        let phone: [String: String] = ["2": "abc", "3": "def", "4": "ghi", "5": "jkl", "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"]
        var output: [String] = []
        func backTrack(combination: String, next_digits: String) {
            if next_digits.count == 0 {
                output.append(combination)
            } else {
                let digit = String(next_digits[next_digits.startIndex..<next_digits.index(next_digits.startIndex, offsetBy: 1)])
                let letters: String = phone[digit] ?? ""
                for i in 0..<letters.count {
                    let start = letters.index(letters.startIndex, offsetBy: i)
                    let end = letters.index(letters.startIndex, offsetBy: i+1)
                    let letter = String(letters[start..<end])
                    backTrack(combination: combination + letter, next_digits: String(next_digits[next_digits.index(next_digits.startIndex, offsetBy: 1)...]))
                }
            }
        }
        if digits.count != 0 {
            backTrack(combination: "", next_digits: digits)
        }
        return output
    }
}