美文网首页LeetCodeSwift 集
LeetCode - #44 通配符匹配

LeetCode - #44 通配符匹配

作者: Swift社区 | 来源:发表于2022-04-17 19:07 被阅读0次

前言

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

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

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

难度水平:困难

1. 描述

给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?''*' 的通配符匹配。

'?' 可以匹配任何单个字符。

'*' 可以匹配任意字符串(包括空字符串)。

两个字符串完全匹配才算匹配成功。

说明:

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 ?*

2. 示例

示例 1

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2

输入:
s = "aa"
p = "*"
输出: true
解释: '*' 可以匹配任意字符串。

示例 3

输入:
s = "cb"
p = "?a"
输出: false
解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。

示例 4

输入:
s = "adceb"
p = "*a*b"
输出: true
解释: 第一个 '*' 可以匹配空字符串, 第二个 '*' 可以匹配字符串 "dce".

示例 5

输入:
s = "acdcb"
p = "a*c?b"
输出: false

3. 答案

class WildcardMatching {
    func isMatch(_ s: String, _ p: String) -> Bool {
        let sChars = Array(s), pChars = Array(p)
        var dp = Array(repeating: Array(repeating: false, count: p.count + 1), count: s.count + 1)
        dp[0][0] = true
        
        // must start from 0, to make range feasible and handle empty vs. * case
        for i in 0...s.count {
            for j in 0...p.count {
                guard j > 0 else {
                    continue
                }
                
                let pCurrent = pChars[j - 1]
    
                if pCurrent != "*" {
                    dp[i][j] = i > 0 && dp[i - 1][j - 1] && (pCurrent == sChars[i - 1] || pCurrent == "?")
                } else {
                    // Two situations:
                    // (1) '*' is the first character in p;
                    // (2) For k>=0 and k<=i, there is some dp[k][j-1] being true;
                    //     and '*' will match the rest sequence in s after index k;
                    var flag = false
                    for k in 0...i {
                        if dp[k][j - 1] {
                            flag = true
                            break
                        }
                    }
                    
                    dp[i][j] = flag || j == 1   
                }
            }
        }
        
        return dp[s.count][p.count]
    }
}
  • 主要思想:经典的二维动态规划。
  • 时间复杂度: O(mn)
  • 空间复杂度: O(mn)

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

点击前往 LeetCode 练习

关于我们

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

后续还会翻译大量资料到我们公众号,有感兴趣的朋友,可以加入我们。

相关文章

  • LeetCode-44-通配符匹配

    LeetCode-44-通配符匹配 来源:力扣(LeetCode)链接:https://leetcode-cn.c...

  • 44. 通配符匹配

    44. 通配符匹配(难度:困难) 题目链接:https://leetcode-cn.com/problems/wi...

  • [LeetCode]44、通配符匹配

    题目描述 给定一个字符串 (s) 和一个字符模式 (p) ,实现一个支持 '?' 和 '*' 的通配符匹配。 '?...

  • LeetCode - #44 通配符匹配

    前言 我们社区陆续会将顾毅(Netflix 增长黑客,《iOS 面试之道》作者,ACE 职业健身教练。微博:@故胤...

  • LeetCode 第 44 题:通配符匹配

    1、前言 2、思路 这道题与第10题的正则表达式匹配一毛一样,甚至连解法都差不多。都是先匹配第一个,如果遇到特殊匹...

  • LeetCode 力扣 44. 通配符匹配

    题目描述(困难难度) 字符串匹配,? 匹配单个任意字符,* 匹配任意长度字符串,包括空串。和第 10 题有些类似。...

  • 44.通配符匹配

  • 44. 通配符匹配

    44. 通配符匹配 字符串dp 类似的还有经典的72. 编辑距离本题是10. 正则表达式匹配的稍简单版本 dp[i...

  • 44. 通配符匹配

    自己解法 这个题有的印象是,用动态规划,p的某一位要判断是否是*。 p不是*的情况下,解法简单,dp[i][j] ...

  • LeetCode第44题: 通配符匹配isMatch(C语言)

    引子 思路:看到两个序列去匹配的问题,最自然的想法是双层循环尝试对齐匹配,我们假设表格数字为1代表匹配成功,0代表...

网友评论

    本文标题:LeetCode - #44 通配符匹配

    本文链接:https://www.haomeiwen.com/subject/ckstjrtx.html