首页 > 代码库 > Wildcard Matching

Wildcard Matching

2024-07-18 08:56:35   221人阅读

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") → falseisMatch("aa","aa") → trueisMatch("aaa","aa") → falseisMatch("aa", "*") → trueisMatch("aa", "a*") → trueisMatch("ab", "?*") → trueisMatch("aab", "c*a*b") → false


第一遍：
 1 public class Solution { 2     public boolean isMatch(String s, String p) { 3         if(p.length() == 0) return s.length() == 0; 4         if(s.length() == 0) return p.length() == 0; 5         if(p.charAt(0) == ‘?‘ || p.charAt(0) == s.charAt(0)) return isMatch(s.substring(1), p.substring(1)); 6         else if(p.charAt(0) == ‘*‘){ 7             for(int i = 0; i < s.length(); i ++){ 8                 if(isMatch(s.substring(i), p.substring(1))) return true; 9             }10             return false;11         }12         else return false;13     }14 }

Time Limit Exceeded

"abbabbbaabaaabbbbbabbabbabbbabbaaabbbababbabaaabbab", "*aabb***aa**a******aa*"

网上做法：

贪心的策略，能匹配就一直往后遍历，匹配不上了就看看前面有没有‘*‘来救救场，再从‘*‘后面接着试。

 1 public class Solution { 2     public boolean isMatch(String s, String p) { 3         int i = 0; 4         int j = 0; 5         int star = -1; 6         int mark = -1; 7         while (i < s.length()){ 8             if (j < p.length() && (p.charAt(j) == ‘?‘ || p.charAt(j) == s.charAt(i))) { 9                 ++i;10                 ++j;11             } else if (j < p.length() && p.charAt(j) == ‘*‘) {12                 star = j++;13                 mark = i;14             } else if (star != -1) {15                 j = star + 1;16                 i = ++mark;17             } else {18                 return false;19             }20         }21         while (j < p.length() && p.charAt(j) == ‘*‘) {// i == s.length()22             ++j;23         }24         return j == p.length();25     }26 }

 

 


联系
我们