LeetCode - #20 有效的括号

简介: 不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。

前言

我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。)的 Swift 算法题题解整理为文字版以方便大家学习与阅读。

LeetCode 算法到目前我们已经更新了 19 期,我们会保持更新时间和进度(周一、周三、周五早上 9:00 发布),每期的内容不多,我们希望大家可以在上班路上阅读,长久积累会有很大提升。

不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。

难度水平:中等

1. 描述

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

2. 示例

示例 1

输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2

输入:digits = ""
输出:[]

示例 3

输入:digits = "2"
输出:["a","b","c"]

约束条件:

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字

3. 答案

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]
    }
}
  • 主要思想:经典的深度优先搜索,首先创建电话板
  • 时间复杂度: O(4^n), n 表示数字长度
  • 空间复杂度: O(n), n 表示数字长度

该算法题解的仓库:LeetCode-Swift

点击前往 LeetCode 练习

关于我们

我们是由 Swift 爱好者共同维护,我们会分享以 Swift 实战、SwiftUI、Swift 基础为核心的技术内容,也整理收集优秀的学习资料。

相关文章
|
7月前
|
存储 C语言 索引
环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】
环形链表、环形链表 II、有效的括号​​​​​​​【LeetCode刷题日志】
|
1月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
2月前
|
算法 C++
Leetcode第二十二题(括号生成)
这篇文章讨论了如何使用递归算法解决LeetCode第22题“括号生成”的问题,提供了两种C++的实现方法,目的是生成所有有效的括号组合。
21 0
Leetcode第二十二题(括号生成)
|
2月前
|
存储 C++ 容器
Leetcode第二十题(有效的括号)
这篇文章介绍了如何使用栈来解决LeetCode第20题“有效的括号”问题,提供了两种方法:数组栈和容器栈,以及相应的C++代码实现。
21 0
|
4月前
|
算法
LeetCode第22题括号生成
该文章介绍了 LeetCode 第 22 题括号生成的解法,通过回溯算法生成所有可能的括号组合,在递归过程中根据左右括号数量的条件进行剪枝,从而得到有效的括号组合。
LeetCode第22题括号生成
|
4月前
|
存储 算法
LeetCode第20题有效的括号
该文章介绍了 LeetCode 第 20 题有效的括号的解法,通过分析有效括号的特征,使用栈结构存储括号关系,判断遇到右边括号时栈顶是否有匹配的左边括号,从而解决问题,同时总结了栈的先进后出结构可用于解决有规律的符号匹配问题。
LeetCode第20题有效的括号
|
4月前
|
算法 Python
【Leetcode刷题Python】括号匹配问题
一种解决括号匹配问题的Python实现方法,通过计算给定括号串的所有子串的最长合法括号子序列长度之和来确定权值。
34 0
|
4月前
|
机器学习/深度学习 Python
【Leetcode刷题Python】22. 括号生成
本文介绍了了LeetCode题目22的两种Python编程解决方案,题目要求生成所有可能的且有效的括号组合,包括暴力求解和回溯方法。
28 0
|
4月前
|
Python
【Leetcode刷题Python】20. 有效的括号
LeetCode上题目“20. 有效的括号”的Python解决方案,使用栈数据结构来验证括号序列的有效性。具体实现中,会在栈中预先放置一个特殊字符以避免在弹出操作时出现空栈错误,并通过匹配左右括号来判断括号序列是否有效。
50 0
|
6月前
|
算法 Java C语言
【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode 20:有效的括号(Java/C/Python3实现含注释说明,Easy)
54 1