[Swift]LeetCode44.通配符匹配|WildcardMatching

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/9907424.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新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 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: false
Explanation: "a" does not match the entire string "aa".

Example 2:

Input:
s = "aa"
p = "*"
Output: true
Explanation: '*' matches any sequence.

Example 3:

Input:
s = "cb"
p = "?a"
Output: false
Explanation: '?' matches 'c', but the second letter is 'a', which does not match 'b'.

Example 4:

Input:
s = "adceb"
p = "*a*b"
Output: true
Explanation: 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 - 1
10     let pp = p.utf8CString
11     let pCount = pp.count - 1
12     
13     let q = "?".utf8CString.first!
14     let star = "*".utf8CString.first!
15     
16     while stringIndex < sCount {
17         if patternIndex < pCount
18             && (pp[patternIndex] == q
19                 || pp[patternIndex] == ss[stringIndex]) {
20             stringIndex += 1
21             patternIndex += 1
22         } else if patternIndex < pCount && pp[patternIndex] == star {
23             starIndex = patternIndex
24             match = stringIndex
25             patternIndex += 1
26         } else if starIndex != -1 {
27             patternIndex = starIndex + 1
28             match += 1
29             stringIndex = match
30         } else {
31             return false
32         }
33     }
34     
35     while patternIndex < pCount && pp[patternIndex] == star {
36         patternIndex += 1
37     }
38     
39     return patternIndex == pCount
40     }
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 = -1
21         var pPreIndex = -1
22         
23         while sIndex < sArray.count {
24             if pIndex >= pArray.count {
25                if sPreIndex != -1 && pPreIndex != -1 {
26                     sIndex = sPreIndex
27                     pIndex = pPreIndex
28                     sPreIndex = -1
29                     pPreIndex = -1
30                     continue
31                 }
32                 return false
33             } else if (pArray[pIndex] != "*" && pArray[pIndex] != "?") && pArray[pIndex] != sArray[sIndex] {
34                if sPreIndex != -1 && pPreIndex != -1 {
35                     sIndex = sPreIndex
36                     pIndex = pPreIndex
37                     sPreIndex = -1
38                     pPreIndex = -1
39                     continue
40                 }
41                 return false
42             } else if pArray[pIndex] == "?" {
43                 pIndex = pIndex + 1
44                 sIndex = sIndex + 1
45             } else if pArray[pIndex] == "*" {
46                 //case 0: * is the last char
47                 if pIndex == pArray.count - 1 {
48                     return true
49                 }
50                 
51                 //case 1: * == null
52                 //case 2: * == multiple char
53                 pIndex = pIndex + 1
54                 while sIndex < sArray.count {
55                     if checkMatch(sArray[sIndex],pArray[pIndex]) {
56                         pPreIndex = pIndex - 1
57                         sPreIndex = sIndex + 1
58                         pIndex = pIndex + 1
59                         sIndex = sIndex + 1
60                         break
61                     }
62                     sIndex = sIndex + 1
63                 }
64             } else if pArray[pIndex] == sArray[sIndex] {
65                 pIndex = pIndex + 1
66                 sIndex = sIndex + 1
67             } else if pArray[pIndex] != sArray[sIndex] {
68                if sPreIndex != -1 && pPreIndex != -1 {
69                     sIndex = sPreIndex
70                     pIndex = pPreIndex
71                     sPreIndex = -1
72                     pPreIndex = -1
73                     continue
74                 }
75                 return false
76             }
77         }
78         if pIndex != pArray.count && !(pIndex == pArray.count - 1 && pArray[pIndex] == "*" ){
79             return false
80         }
81         return true
82     }
83     
84     func checkMatch(_ char1: Character, _ char2:Character) -> Bool {
85         if char1 == char2 || char2 == "?" {
86             return true
87         } else {
88             return false
89         }
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 = -1
10         
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 += 1
17                 pc += 1
18             } else if pc < p.count && pA[pc] == "*" {
19                 startIndex = pc
20                 last = sc
21                 pc += 1
22             } else if startIndex != -1 {
23                 pc = startIndex + 1
24                 last += 1
25                 sc = last
26             } else {
27                 return false
28             }
29         }
30         
31          while (pc < p.count && pA[pc] == "*") {
32             pc += 1
33          }
34         
35         return pc == p.count
36     }
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 += 1
10                 pIndex += 1
11             } else if pIndex < p.count && p[pIndex] == "*" {
12                 startIndex = pIndex
13                 match = sIndex
14                 pIndex += 1
15             } else if startIndex != -1 {
16                 pIndex = startIndex + 1
17                 match += 1
18                 sIndex = match
19             } else {
20                 return false
21             }
22         }
23         while pIndex < p.count && p[pIndex] == "*" {
24             pIndex += 1
25         }
26         return pIndex == p.count
27     }
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+=1
10             j+=1
11         } else if j < p.count && Array(p)[j] == Character("*") {
12             match = i
13             star = j
14             j+=1
15         } else if star != -1 {
16             j = star + 1
17             match+=1
18             i = match
19         } else {
20             return false
21         }
22     }
23     while j < p.count && Array(p)[j] == Character("*") {j+=1}
24     return j == p.count
25     }
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] = true
11             } else {
12                 break
13             }
14         }
15 
16         for sPos in stride(from:1,to:s.count,by:1) {
17             for pPos in stride(from:1,to:p.count,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 }