[Swift]LeetCode44. 通配符匹配 | Wildcard Matching（通配符字符串匹配）

25-04-21 2

本文将带您了解关于[Swift]LeetCode44.通配符匹配|WildcardMatching的新内容，同时我们还将为您解释通配符字符串匹配的相关知识，另外，我们还将为您提供关于44.通配符匹配、

本文将带您了解关于[Swift]LeetCode44. 通配符匹配 | Wildcard Matching的新内容，同时我们还将为您解释通配符字符串匹配的相关知识，另外，我们还将为您提供关于44. 通配符匹配、44. 通配符匹配（难度：困难）、cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration can be found for element ''dubbo:application''.、cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration 的解决的实用信息。

本文目录一览：

[Swift]LeetCode44. 通配符匹配 | Wildcard Matching（通配符字符串匹配）
44. 通配符匹配
44. 通配符匹配（难度：困难）
cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration can be found for element ''dubbo:application''.
cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration 的解决

[Swift]LeetCode44. 通配符匹配 | Wildcard Matching（通配符字符串匹配）

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

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 }

44. 通配符匹配

给定一个字符串 (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 = "ab"
输出: true
解释: 第一个 '''' 可以匹配空字符串, 第二个 '''' 可以匹配字符串 "dce".
示例 5:

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

有点像第10题，匹配字符串可以对应原串多种情况，可以用dfs，也可以用dp来储存状态，注意当s为“”，也要计算dp值

public boolean isMatch(String s, String p) {
    boolean[][] dp=new boolean[s.length()+1][p.length()+1];
    dp[0][0]=true;
    for(int i=0;i<=s.length();i++){
        for(int j=1;j<=p.length();j++){
            char c1='' '';
            char c2='' '';
            if(i>=1) c1=s.charAt(i-1);
            if(j>=1) c2=p.charAt(j-1);
            if(c1==c2 || (c1!='' '' && c2==''?'')){
                dp[i][j]=dp[i-1][j-1];
            }else if(c2==''*''){
                if(c1=='' '') {
                    dp[0][j]=dp[0][j-1];
                }else{
                    dp[i][j]=dp[i-1][j-1] || dp[i][j-1] || dp[i-1][j];
                }
            }
        }
    }
    return dp[s.length()][p.length()];
}

44. 通配符匹配（难度：困难）

题目链接：https://leetcode-cn.com/problems/wildcard-matching/

问题描述：

给定一个字符串 (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

解法一：动态规划

我们可以利用动态规划的思想来解决这道问题。

首先我们可以创建一个存储状态的二维数组 dp[][]来存储s字符串的每个位置和p字符串的每个位置是否匹配。即 dp[i][j] = true 表示s串从0到i-1的子串与 p串从0到j-1的子串匹配。

里面状态存储，可以解决重复子问题，从而提高算法的效率。

来分析可能遇到的情况：

（1）当p[i-1] = s[j-1] 或者 p[i-1] = '?' 时，都满足当前匹配的原则，所以 dp[i][j] = dp[i-1][j-1];

（2）当 p[i-1] = '*' 时，‘*’ 可能有两种情况，可能代表一个空串，也可能是任意字符串，那么就分为两种情况然后取并集（只要有一种满足即可），所以 dp[i][j] = dp[i-1][j] | dp[i][j-1] ;

特殊情况处理：

（1）若模式串中存在连续的的 *，连续的 * 和一个*效果是一样的，但是会增加很多不必要的递归，所以我们先对模式串进行处理，让连续的多个 * 合并为一个，再让他进行动态规划。

（2）而且若 p[0] = '*'的话，按理说应该不管s是 dp[1][0] = true，这种特殊情况也需要先处理，不然，直接进行 dp[i][j] = dp[i-1][j] | dp[i][j-1]的话，会得到false。

代码：

class Solution {
  	public boolean isMatch(String s, String p) {
		StringBuilder pBuilder = new StringBuilder(p);
		for(int i = 1;i<pBuilder.length();i++) {
			if (pBuilder.charat(i) == '*' && pBuilder.charat(i-1) == '*') {
				pBuilder.deleteCharat(i);
				i--;
            }
		}
		p = pBuilder.toString();
		int sLen = s.length();
		int pLen = p.length();
		boolean dp[][] = new boolean[pLen+1][sLen+1];
		dp[0][0] = true;
        if(pLen > 0 && p.charat(0) == '*')
        	dp[1][0] = true;


		for(int i =1;i<=pLen;i++) {
			for(int j = 1;j<=sLen;j++) {
				if(p.charat(i-1) == s.charat(j-1) || p.charat(i-1)=='?') {
					dp[i][j] = dp[i-1][j-1];
				}else if(p.charat(i-1) == '*') {
					dp[i][j] = dp[i-1][j] | dp[i][j-1];
				}
			}
		}
		return dp[pLen][sLen];
	}
}

cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration can be found for element ''dubbo:application''.

cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration 的解决

导入了一个工程，编译什么的都还好，但是报了一个 XML 的错误。
cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration can be found for element ''dubbo:application''.

具体错误如下：

Multiple annotations found at this line:
   - cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration can be found for element ''dubbo:application''.
   - schema_reference.4: Failed to read schema document ''http://code.alibabatech.com/schema/dubbo/dubbo.xsd'', because 1) could not find the
   document; 2) the document could not be read; 3) the root element of the document is not <xsd:schema>.

根据错误提示，有可能是 http://code.alibabatech.com/schema/dubbo/dubbo.xsd 这个文档找不到或者打不开，于是百度了一下，发现类似问题的问还是比较多的，比较轻松找到解决办法。大致的思路是，到网上下载一个 dubbo.xsd 文件，其实在 dubbo 的 jar 包里就有，直接解压出来就好，放到本地目录，然后在 Eclipse 里配置上关联关系，让 Eclipse 能找到这个文件即可。

1、下载一个 dubbo.xsd 文件；
　　2、在 windows->preferrence->xml->xmlcatalogadd->catalog entry ->file system 选择刚刚下载的文件路径；
　　3、修改 key 值和配置文件的 http://code.alibabatech.com/schema/dubbo/dubbo.xsd 相同保存。
　　4、在 xml 文件右键 validate 就可以 k 解决了。

后记：有其它的 xsd 文件找不到的情况，也可以按照类似的方法解决。

转自 https://blog.csdn.net/ddshang/article/details/72772640

今天关于[Swift]LeetCode44. 通配符匹配 | Wildcard Matching和通配符字符串匹配的分享就到这里，希望大家有所收获，若想了解更多关于44. 通配符匹配、44. 通配符匹配（难度：困难）、cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration can be found for element ''dubbo:application''.、cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration 的解决等相关知识，可以在本站进行查询。

本文标签：