首页 > 代码库 > 44. Wildcard Matching

44. Wildcard Matching

2024-10-23 15:47:39   210人阅读

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


递归完美解答，然而超时了
public class Solution {
    public boolean isMatch(String s, String p) {
        if (s.length()==0){
            if ( p.length()>0&&p.charAt(0)==‘*‘){
                return isMatch(s,p.substring(1));
            }else {
                return p.length() == 0;
            }
        }
        if (p.length()==0){
            return s.length()==0;
        }
        if (p.charAt(0)==‘?‘){
            return isMatch(s.substring(1),p.substring(1));
        }else if(p.charAt(0)==‘*‘) {
            return isMatch(s.substring(1),p)||isMatch(s,p.substring(1));
        }else {
            if (p.charAt(0)==s.charAt(0)){
                return isMatch(s.substring(1),p.substring(1));
            }else {
                return false;
            }
        }
    }
}

所以考虑用回溯。

此博客讲解的很详细，http://blog.csdn.net/u012848330/article/details/52596618

int bp=-1;
       int bs=-1;
       int i=0;
       int j=0;
       while (i<s.length()){
           if (j<p.length()&&p.charAt(j)==‘*‘){
               j++;
               bp=j;
               bs=i;
           }
           else if (j<p.length()&&(p.charAt(j)==‘?‘||p.charAt(j)==s.charAt(i))){
                i++;
                j++;
           }else if(bp!=-1){
               j=bp;
               i=++bs;
           }
           else {
               break;
           }
       }
       while (j<p.length()&&p.charAt(j)==‘*‘){
           j++;
       }
        return i==s.length()&&j==p.length();

 

44. Wildcard Matching


联系
我们