[Swift]LeetCode44. 通配符匹配 | Wildcard Matching_app

概述Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?‘ and ‘*‘. ‘?‘ Matches any single character.‘*‘ Matches any sequence of characters (including the

Given an input string (s) and a pattern (p),implement wildcard pattern matching with support for ‘?‘ and ‘*‘.

‘?‘ Matches any single character.‘*‘ Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

Note:

s Could be empty and contains only lowercase letters a-z. p Could be empty and contains only lowercase letters a-z,and characters like ? or *.

Example 1:

input:s = "aa"p = "a"Output: falseExplanation: "a" does not match the entire string "aa".

Example 2:

input:s = "aa"p = "*"Output: trueExplanation: ‘*‘ matches any sequence.

Example 3:

input:s = "cb"p = "?a"Output: falseExplanation: ‘?‘ matches ‘c‘,but the second letter is ‘a‘,which does not match ‘b‘.

Example 4:

input:s = "adceb"p = "*a*b"Output: trueExplanation: The first ‘*‘ matches the empty sequence,while the second ‘*‘ matches the substring "dce".

Example 5:

input:s = "acdcb"p = "a*c?b"Output: false

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

‘?‘ 可以匹配任何单个字符。‘*‘ 可以匹配任意字符串（包括空字符串）。

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

说明:

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

示例 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

36ms

 1 class Solution { 2     func isMatch(_ s: String,_ p: String) -> Bool { 3         var stringIndex = 0 4     var patternIndex = 0 5     var match = 0 6     var starIndex = -1 7      8     let ss = s.utf8CString 9     let sCount = ss.count - 110     let pp = p.utf8CString11     let pCount = pp.count - 112     13     let q = "?".utf8CString.first!14     let star = "*".utf8CString.first!15     16     while stringIndex < sCount {17         if patternIndex < pCount18             && (pp[patternIndex] == q19                 || pp[patternIndex] == ss[stringIndex]) {20             stringIndex += 121             patternIndex += 122         } else if patternIndex < pCount && pp[patternIndex] == star {23             starIndex = patternIndex24             match = stringIndex25             patternIndex += 126         } else if starIndex != -1 {27             patternIndex = starIndex + 128             match += 129             stringIndex = match30         } else {31             return false32         }33     }34     35     while patternIndex < pCount && pp[patternIndex] == star {36         patternIndex += 137     }38     39     return patternIndex == pCount40     }41 }

48ms

 1 class Solution { 2     func isMatch(_ s: String,_ p: String) -> Bool { 3         var sIndex = 0 4         var pIndex = 0 5          6         var pArray = Array(p) 7         var deleteArray = Array<Int>() 8         for (index,value) in pArray.enumerated() { 9             if index > 0 && value == "*" && value==pArray[index-1] {10                 deleteArray.append(index)11             }12         }13         14         for index in deleteArray.reversed() {15             pArray.remove(at:index)16         }17         18         var sArray = Array(s)19         20         var sPreIndex = -121         var pPreIndex = -122         23         while sIndex < sArray.count {24             if pIndex >= pArray.count {25                if sPreIndex != -1 && pPreIndex != -1 {26                     sIndex = sPreIndex27                     pIndex = pPreIndex28                     sPreIndex = -129                     pPreIndex = -130                     continue31                 }32                 return false33             } else if (pArray[pIndex] != "*" && pArray[pIndex] != "?") && pArray[pIndex] != sArray[sIndex] {34                if sPreIndex != -1 && pPreIndex != -1 {35                     sIndex = sPreIndex36                     pIndex = pPreIndex37                     sPreIndex = -138                     pPreIndex = -139                     continue40                 }41                 return false42             } else if pArray[pIndex] == "?" {43                 pIndex = pIndex + 144                 sIndex = sIndex + 145             } else if pArray[pIndex] == "*" {46                 //case 0: * is the last char47                 if pIndex == pArray.count - 1 {48                     return true49                 }50                 51                 //case 1: * == null52                 //case 2: * == multiple char53                 pIndex = pIndex + 154                 while sIndex < sArray.count {55                     if checkMatch(sArray[sIndex],pArray[pIndex]) {56                         pPreIndex = pIndex - 157                         sPreIndex = sIndex + 158                         pIndex = pIndex + 159                         sIndex = sIndex + 160                         break61                     }62                     sIndex = sIndex + 163                 }64             } else if pArray[pIndex] == sArray[sIndex] {65                 pIndex = pIndex + 166                 sIndex = sIndex + 167             } else if pArray[pIndex] != sArray[sIndex] {68                if sPreIndex != -1 && pPreIndex != -1 {69                     sIndex = sPreIndex70                     pIndex = pPreIndex71                     sPreIndex = -172                     pPreIndex = -173                     continue74                 }75                 return false76             }77         }78         if pIndex != pArray.count && !(pIndex == pArray.count - 1 && pArray[pIndex] == "*" ){79             return false80         }81         return true82     }83     84     func checkMatch(_ char1: Character,_ char2:Character) -> Bool {85         if char1 == char2 || char2 == "?" {86             return true87         } else {88             return false89         }90     }91     92 }

80ms

 1 class Solution { 2     func isMatch(_ s: String,_ p: String) -> Bool { 3         if s.count == 0 && p.count == 0 { 4             return true 5         } 6         var sc = 0 7         var pc = 0 8         var startIndex = -1 9         var last = -110         11         var sA = Array(s)12         var pA = Array(p)13         14         while sc < s.count {15             if pc < p.count && (sA[sc] == pA[pc] || pA[pc] == "?") {16                 sc += 117                 pc += 118             } else if pc < p.count && pA[pc] == "*" {19                 startIndex = pc20                 last = sc21                 pc += 122             } else if startIndex != -1 {23                 pc = startIndex + 124                 last += 125                 sc = last26             } else {27                 return false28             }29         }30         31          while (pc < p.count && pA[pc] == "*") {32             pc += 133          }34         35         return pc == p.count36     }37 }

160ms

 1 class Solution { 2     func isMatch(_ s: String,_ p: String) -> Bool { 3         var sIndex = 0 4         var pIndex = 0 5         var match = 0 6         var startIndex = -1 7         while sIndex < s.count { 8             if pIndex < p.count && (p[pIndex] == "?" || s[sIndex] == p[pIndex]) { 9                 sIndex += 110                 pIndex += 111             } else if pIndex < p.count && p[pIndex] == "*" {12                 startIndex = pIndex13                 match = sIndex14                 pIndex += 115             } else if startIndex != -1 {16                 pIndex = startIndex + 117                 match += 118                 sIndex = match19             } else {20                 return false21             }22         }23         while pIndex < p.count && p[pIndex] == "*" {24             pIndex += 125         }26         return pIndex == p.count27     }28 }29 30 private extension String {31     subscript(index: Int) -> Character {32         return self[self.index(self.startIndex,offsetBy: index)]33     }34 }

716ms

 1 class Solution { 2     func isMatch(_ s: String,_ p: String) -> Bool { 3          var i = 0 4     var j = 0 5     var match = 0 6     var star = -1 7     while i < s.count { 8         if j < p.count && (Array(s)[i] == Array(p)[j] || Array(p)[j] == Character("?")) { 9             i+=110             j+=111         } else if j < p.count && Array(p)[j] == Character("*") {12             match = i13             star = j14             j+=115         } else if star != -1 {16             j = star + 117             match+=118             i = match19         } else {20             return false21         }22     }23     while j < p.count && Array(p)[j] == Character("*") {j+=1}24     return j == p.count25     }26 }

760ms

 1 class Solution { 2     func isMatch(_ s: String,_ p: String) -> Bool { 3         var s = ["a"] + Array(s) 4         var p = ["a"] + Array(p) 5         var dp = Array(repeating:Array(repeating:false,count:p.count),count:s.count) 6         dp[0][0] = true //"a" == "a" 7          8         for pPos in strIDe(from:1,to:p.count,by:1) { 9             if p[pPos] == "*" {10                 dp[0][pPos] = true11             } else {12                 break13             }14         }15 16         for sPos in strIDe(from:1,to:s.count,by:1) {17             for pPos in strIDe(from:1,by:1) {18                 if p[pPos] == "*" {19                     dp[sPos][pPos] = dp[sPos - 1][pPos] || dp[sPos][pPos - 1]20                 } else {21                     dp[sPos][pPos] = dp[sPos - 1][pPos - 1] && (s[sPos] == p[pPos] || p[pPos] == "?")22                 }23                 24             }25         }26 27         return dp[s.count - 1][p.count - 1]28     }29 }