首页 > 代码库 > Wildcard Matching

Wildcard Matching

2024-07-04 18:04:39   225人阅读

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).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

首先想到的是递归，但是超时，然后递归转非递归，在大数据测试用例时还是超时，这里贴一下非递归的代码

 

 1 public boolean isMatch(String s, String p) {
 2         Stack<String> source = new Stack<String>();
 3         Stack<String> regex = new Stack<String>();
 4         if (s.equals("")) {
 5             if (p.equals("") || p.equals("*")) {
 6                 return true;
 7             } else {
 8                 return false;
 9             }
10         }
11         char temp[] = p.toCharArray();
12         p = "";
13         for (char a : temp) {
14             if (p.length() > 0 && p.charAt(p.length() - 1) == ‘*‘ && a == ‘*‘) {
15                 continue;
16             }
17             p += a;
18         }
19         boolean result = false;
20         source.push(s);
21         regex.push(p);
22         while (!result && !source.empty()) {
23             s = source.pop();
24             p = regex.pop();
25             int i = 0;
26             int j = 0;
27             for (; i < s.length() && j < p.length();) {
28                 if (p.charAt(j) != ‘*‘) {
29                     if (p.charAt(0) == ‘?‘ || p.charAt(0) == s.charAt(0)) {
30                         i++;
31                         j++;
32                     } else {
33                         break;
34                     }
35                 } else {
36                     j++;
37                     if (j == p.length()) {
38                         i = s.length();
39                     } else {
40                         for (int k = i; k < s.length(); k++) {
41                             if (s.charAt(k) == p.charAt(j)) {
42                                 source.push(s.substring(k));
43                                 regex.push(p.substring(j));
44                             }
45                         }
46                         continue;
47                     }
48                 }
49             }
50             if (i == s.length() && j == p.length()) {
51                 result = true;
52             }
53         }
54         return result;
55     }

优化后还是超时，就想着应该有别的思路。

借鉴一下网上的，转载自 http://blog.csdn.net/pickless/article/details/9787227

看着有点像求字符串的最长公共子串那个问题的解法

用矩阵表示匹配结果，横坐标为p串，纵坐标为s串，假设S="ababa"，P="a*?"，则有下图：

S\P a * ?
a T T F
b F T T
a F T T
b F T T

如何计算这个表格呢？规则如下：

1. p[j] == ‘*‘，则   f[i][j] = f[i-1][j]

2. p[j] == ‘?‘ || p[j] == s[i] 则 f[i][j] = f[i-1][j-1]

3. 其余情况   f[i][j] = false

上述情况不包含，第0行和第0列，需要单独计算

经过上面分析，第i行只与第i-1行有关，所以，可以将矩阵简化成一维的。代码如下：

 1 public boolean isMatch(String s, String p) {
 2         boolean f[] = new boolean[p.length()];
 3         if (s == null || p == null || (p.equals("") && !s.equals(""))) {
 4             return false;
 5         }
 6         if (s.equals("")) {
 7             if (p.equals("") || p.equals("*")) {
 8                 return true;
 9             } else {
10                 return false;
11             }
12         }
13         boolean isTrue = false;
14         for (int i = 0; i < p.length(); i++) {
15             if (p.charAt(i) == ‘*‘) {
16                 f[i] = (i == 0) || f[i - 1];
17             } else if (p.charAt(i) == ‘?‘ || p.charAt(i) == s.charAt(0)) {
18                 if (isTrue) {
19                     break;
20                 }
21                 f[i] = (i == 0) || ((!isTrue) && f[i - 1]);
22                 isTrue = true;
23             } else {
24                 break;
25             }
26         }
27         for (int i = 1; i < s.length(); i++) {
28             boolean temp[] = new boolean[f.length];
29             for (int j = 0; j < f.length; j++) {
30                 if (p.charAt(j) == ‘*‘) {
31                     temp[j] = f[j];
32                 } else if (p.charAt(j) == ‘?‘ || p.charAt(j) == s.charAt(i)) {
33                     temp[j] = (j == 0 && p.charAt(0) == ‘*‘ && f[j])
34                             || (j > 0 && f[j - 1]);
35                 } else {
36                     temp[j] = false;
37                 }
38             }
39             f = temp;
40         }
41         return f[f.length - 1];
42     }

但是依旧超时，再根据网上的解法，使用贪心算法

http://blog.unieagle.net/2012/11/07/leetcode题目：wildcard-matching/
先用*号把string p切割，然后把每段不含星号的子串放到s中匹配，匹配上了将base前移，继续匹配下一个。这里要注意的是，当p的一头或者一尾没有星号时，第一个和最后一个子串要严格匹配给s的头和尾
成功过大数据
 1 public boolean isMatch(String s, String p) {
 2         int ls = s.length();
 3         int lp = p.length();
 4         if(ls == 0 && lp == 0) return true;
 5         else if(ls != 0 && lp == 0) return false;
 6         
 7         String[] strarr = p.split("[\\*]+",0);
 8         if(strarr.length == 0) return true;
 9         boolean firstneedmatch = !p.startsWith("*");
10         boolean lastneedmatch = !p.endsWith("*");
11         if(!firstneedmatch) strarr = Arrays.copyOfRange(strarr, 1, strarr.length);
12         if(strarr.length == 0) return true;
13         
14         int base = 0;
15         for(int i=0;i<strarr.length;i++){
16             if(base > ls-strarr[i].length()) return false;
17             if(i==0 && firstneedmatch) base = -1;
18             else if(i==strarr.length-1 && lastneedmatch) base = -2;
19             base = getMatchedIdx(s,strarr[i],base);
20             if(base == -1) return false;
21             if(i == strarr.length-1 && lastneedmatch && base != ls) return false;
22         }
23         return true;
24     }
25     
26     public int getMatchedIdx(String s, String pat,int base){
27         char[] sch = s.toCharArray();
28         char[] pch = pat.toCharArray();
29         int ls = sch.length;
30         int lp = pch.length;
31         if(base == -1){
32             for(int i=0;i<lp;i++){
33                 if(pch[i] != ‘?‘ && pch[i] != sch[i]) return -1;
34             }
35             return lp;
36         }
37         else if(base == -2){
38             base = ls-lp;
39             for(int i=0;i<lp;i++){
40                 if(pch[i] !=‘?‘ && pch[i] != sch[base+i]) return -1;
41             }
42             return ls;
43         }
44         else{
45             int limit = ls-lp;
46             for(;base<=limit;base++){
47                 for(int i=0;i<lp;i++){
48                     if(pch[i] !=‘?‘ && pch[i] != sch[base+i]) break;
49                     if(i == lp-1) return base+lp;
50                 }
51             }
52             return -1;
53         }
54     }

 


联系
我们