preface

Our community will gradually organize the Swift Algorithm Solutions of Gu Yi (Netflix growth hacker, author of iOS interview, ACE professional fitness coach. Microblog: @ Taoist Gu Yin [1]) into text versions to facilitate everyone's learning and reading.

So far, we have updated 16 issues of LeetCode algorithm. We will keep the update time and progress (released at 9:00 a.m. on Monday, Wednesday and Friday). There is not much content in each issue. We hope you can read it on the way to work and the long-term accumulation will be greatly improved.

Little steps, no even thousands of miles; If you don't accumulate small streams, you can't become a river and sea. Swift community will accompany you forward. If you have any suggestions and comments, please leave a message at the end of the article. We will try our best to meet your needs.

Difficulty level: medium

1. Description

Given a string containing only the numbers 2-9, returns all the letter combinations it can represent. The answers can be returned in any order.

The number to letter mapping is given as follows (the same as the telephone key). Note that 1 does not correspond to any letter.

2. Examples

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 number in the range ['2 ','9']

3. Answer

class LetterCombinationsPhoneNumber {
    func letterCombinations(_ digits: String) -> [String] {
        guard digits.count > 0 else {
            return [String]()
        }
        
        var combinations = [String](), combination = ""
        let numberToStr = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        
        dfs(&combinations, &combination, numberToStr, digits, 0)
        
        return combinations
    }
    
    private func dfs(_ combinations: inout [String], _ combination: inout String, _ numberToStr: [String], _ digits: String, _ index: Int) {
        if combination.count == digits.count {
            combinations.append(combination)
            return
        }
        
        let currentStr = fetchCurrentStr(from: digits, at: index, numberToStr)
        
        for char in currentStr {
            combination.append(char)
            dfs(&combinations, &combination, numberToStr, digits, index + 1)
            combination.removeLast()
        }
    }
        
    private func fetchCurrentStr(from digits: String, at index: Int, _ numberToStr: [String]) -> String {
        guard index >= 0 && index < digits.count else {
            fatalError("Invalid index")
        }
        
        let currentDigitChar = digits[digits.index(digits.startIndex, offsetBy: index)]
        
        guard let currentDigit = Int(String(currentDigitChar)), currentDigit >= 0, currentDigit < numberToStr.count else {
            fatalError("Invalid digits")
        }
        
        return numberToStr[currentDigit]
    }
}

• Main idea: Classic depth first search, first create a telephone board
• Time complexity: O(4^n), n represents the length of the number
• Spatial complexity: O(n), n represents the length of the number

The warehouse of the algorithm solution: leetcode swift [2]

Click to go to LeetCode[3] to practice

About us

Swift community is a public organization jointly maintained by Swift enthusiasts. We are mainly operated by WeChat official account in China. We will share the technical content with the core of Swift real combat, SwiftUl and Swift, and also collect and collect excellent learning materials.

Special thanks to every editor of Swift community editorial office, thanks for your hard work, providing quality content for Swift community, contributing to the development of Swift language, ranking in different places: Zhang Anyu @ Microsoft [4], Dai Ming @ fast [5], Kwai Fei @ESP[6], Ni Yao @Trip.com[7], Du Xinyao @ Sina [8], Wei Xian @ Gwell[9], Zhang Hao @ iFLYTEK [10], Zhang Xingyu @ ByteDance[11], Guo Yingdong @ convenience bee [12]

reference material

[1] @ so Taoist priest Yin: https://m.weibo.cn/u/1827884772

[2]LeetCode-Swift: https://github.com/soapyigu/LeetCode-Swift

[3]LeetCode: https://leetcode.com/problems/letter-combinations-of-a-phone-number

[4] Zhang Anyu: https://blog.csdn.net/mobanchengshuang

[5] Dai Ming: https://ming1016.github.io

[6] Zhan Fei: https://github.com/fanbaoying

[7] Ni Yao: https://github.com/niyaoyao

[8] Du Xinyao: https://weibo.com/u/3878455011

[9] Wei Xian: https://www.jianshu.com/u/855d6ea2b3d1

[10] Zhang Hao: https://github.com/zhanghao19920218

[11] Zhang Xingyu: https://github.com/bestswifter

[12] Guo Yingdong: https://github.com/EmingK