通配符匹配_

JacobGo！

二刷，修改了一下dp数组更新的顺序，比较好理解

public boolean isMatch(String s, String p) {
    int row = s.length();
    int col = p.length();
    boolean[][] dp = new boolean[row + 1][col + 1];
    dp[0][0] = true;
    for (int j = 1; j < col + 1; j++) {
        if (dp[0][j - 1]) {
            if (p.charAt(j - 1) == '*')
                dp[0][j] = true;
            else
                break;
        }
    }
    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++) {
            if (p.charAt(j) == s.charAt(i) || p.charAt(j) == '?')
                dp[i + 1][j + 1] = dp[i][j];
            else if (p.charAt(j) == '*') {
                dp[i + 1][j + 1] = dp[i][j] || dp[i + 1][j] || dp[i][j + 1];
            }
        }

    return dp[row][col];
}

编辑于 2018-01-06 21:19:47 回复(6)

牛客3857197号

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
         int i=0;
         int j=0;
         int indexstar=-1,indexmatch=0;
        while(s[i]!='\0')
        {
            //最简单的就是
            if(p[j]!='\0' && ( s[i]==p[j] || p[j]=='?' ) )
            {
                i++;
                j++;
            }
            else if(p[j]!='\0' && p[j]=='*')//有*的情况下,先忽略*,看不用*能走多远
            {
                indexmatch=i;
                indexstar=j;//把*的位置记下来
                j++;
            }
            else if(indexstar!=-1) //上面两种都不符合,那就值靠*来解决了
            {
                j=indexstar+1;
                indexmatch++;
                i=indexmatch;//从s后面一个开始,相当于第i个用*表示了
            }
            else //没得救了就返回false吧
            {
                return false;
            }
        }
        while(p[j]!='\0' && p[j]=='*')//去除多余的*号
                  j++;
        return p[j]=='\0';
    }
};

编辑于 2018-03-28 14:23:58 回复(0)

后劲好大

public class Solution {
    public boolean isMatch(String s, String p) {
        if((s == null && p == null) || (s.length() == 0 && p.length() == 0))
        	return true;
        if(p.length() == 0 && s.length() != 0)
        	return false;
       
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        for(int i = 1; i <= p.length(); i++){
        	// 第一行，匹配字符为空，所以考虑待匹配字符为*的情况
        	if(p.charAt(i - 1) == '*')
        		dp[0][i] = dp[0][i-1];
        }
        for(int i = 1; i <= s.length(); i++){
        	for(int j = 1; j <= p.length(); j++){
        		if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?')
        			dp[i][j] = dp[i-1][j-1];
        		if(p.charAt(j - 1) == '*')
        			dp[i][j] = dp[i][j-1] || dp[i-1][j];
        	}
        }
        
        return dp[s.length()][p.length()];
    }
}

发表于 2017-06-05 20:29:56 回复(0)

Java

詆調壹點

public class Solution {
    public boolean isMatch(String s, String p) {
		if(p.length() == 0) {
			if(s.length() == 0) return true;
			else return false;
		}
		boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
		dp[0][0] = true;
		for (int i = 1; i < dp[0].length; i ++ ) { // 处理第一行,注意多个"*"的情况
			if(p.charAt(i - 1) == '*') dp[0][i] = dp[0][i - 1];
		}
		for (int i = 1; i < dp.length; i ++ ) {
			for (int j = 1; j < dp[0].length; j ++ ) {
				if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') dp[i][j] = dp[i - 1][j - 1];
				if(p.charAt(j - 1) == '*') dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
			}
		}
		return dp[dp.length - 1][dp[0].length - 1];
	}
}

编辑于 2016-11-05 21:36:38 回复(0)

viser_zj

class Solution {
public:
	bool isMatch(const char *s, const char *p) {
		int sLen = strlen(s),sIndex = 0;
		int pLen = strlen(p),pIndex = 0;
		int ppre = 0,ipre = 0;
		bool flag = false;
		while (sIndex<sLen) {
			if (s[sIndex]==p[pIndex] || p[pIndex]=='?'){
				++sIndex,++pIndex;
			}else if (p[pIndex]=='*'){    //跳过并记录*后面开始匹配的索引
				ppre = ++pIndex;
				ipre = sIndex;            //记录s中开始与*后面匹配的索引
				flag = true;
			}else{
				if (flag){                //无法匹配，在出现*情况下用*弥补
					sIndex = ++ipre;
					pIndex = ppre;
				}else{
					return false;
				}
			}
		}
		while (p[pIndex]=='*') {          //将剩余的*匹配掉
			++pIndex;
		}
		return pIndex==pLen&&sIndex==sLen;
	}
};

发表于 2016-08-19 10:22:48 回复(1)

JavaScript

splwany


	function isMatch(s, p) {
    // s 的指针，p 的指针，s 的新起始位置， p 最新出现 '*' 的位置
    let sIndex = 0, pIndex = 0, sStart = 0, star = null;
    while (s[sIndex]) {
        // 当 p 读到 '?' 或 p 当前字符与 s 匹配时，s 和 p 的指针同时后移一位
        if (p[pIndex] === '?' || p[pIndex] === s[sIndex]) sIndex++, pIndex++;
        // 当 p 读到 '*' 时，记录当前 s 的位置为新的起始位置，记录 '*' 的新位置，p的指针后移一位
        else if (p[pIndex] === '*') sStart = sIndex, star = pIndex++;
        // 当 p 出现过 '*' 且 p 当前位置的字符与 s 当前位置的字符不匹配时，s 的起始位置和 s 的指针同时后移一位，p 的指针重新从 '*' 的后一位开始
        else if (star !== null) sIndex = ++sStart, pIndex = star + 1;
        // 如果既没出现过 '?' 或 '*'，也没有匹配的字符，直接返回 false
        else return false;
    }
    // 跳过后面的所有 '*'
    while (p[pIndex] === '*') pIndex++;
    // 如果 p 的指针在 p 的末尾，说明模式匹配正确
    return pIndex === p.length;
}

编辑于 2021-04-20 16:05:18 回复(0)

C/C++

ltaoj

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int row = strlen(s);
        int col = strlen(p);
        // 这里一开始写成了 strlen(s); ...
        vector<vector<bool>> dp(row + 1, vector<bool>(col + 1, false));
        dp[0][0] = true;
        for (int j = 1;j < col + 1;j++) {
            if (p[j - 1] == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }
        for (int i = 0;i < row;i++) {
            for (int j = 0;j < col;j++) {
                if (p[j] == s[i] || p[j] == '?') {
                    dp[i + 1][j + 1] = dp[i][j];
                } else if (p[j] == '*') {
                    dp[i + 1][j + 1] = dp[i][j] || dp[i + 1][j] || dp[i][j + 1];
                }
            }
        }
        return dp[row][col];
    }
};

发表于 2019-12-30 00:33:54 回复(0)

Java

齐鱼鱼

public class WildCardMatching {          public boolean isMatch(String s, String p) {
        int n=s.length();
        int m=p.length();
        boolean [][] dp=new boolean[n+1][m+1];
        dp[n][m]=true;
        for(int i=p.length()-1;i>=0;i--){
            if(p.charAt(i)=='*'){
                dp[n][i]=true;
            }else{
                break;
            }
        }
        for(int i=n-1;i>=0;i--){
            for(int j=m-1;j>=0;j--){
                if(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?'){
                    dp[i][j]=dp[i+1][j+1];
                }else if(p.charAt(j)=='*'){
                    dp[i][j]=dp[i+1][j]||dp[i][j+1];
                }else{
                    dp[i][j]=false;
                }
            }
        }
        return dp[0][0];
    }
}
raodanwoyiranxihuanni

发表于 2018-09-22 14:27:39 回复(0)

白银之鹰

O(n)


	import java.util.*;



	public class Solution {
    boolean equal(String s, String p) {
        if (s.length() != p.length()) {
            return false;
        }
        for (int i = 0; i < s.length(); i++) {
            if (p.charAt(i) != '?' && s.charAt(i) != p.charAt(i)) {
                return false;
            }
        }
        return true;
    }



	    int indexOf(String s, String sub, int fromIndex) {
        int endI = s.length() - sub.length();
        for (int i = fromIndex; i <= endI; i++) {
            int j = i;
            for (; j < i + sub.length(); j++) {
                if (sub.charAt(j - i) != '?' && s.charAt(j) != sub.charAt(j - i)) {
                    break;
                }
            }
            if (j - i == sub.length()) {
                return i;
            }
        }



	        return -1;
    }



	    public boolean isMatch(String s, String p) {



	        //p中最左边'*'号位置
        int ps = p.indexOf('*');
        //p中最右边'*'号位置
        int pe = p.lastIndexOf('*');
        int pre = ps;
        int rear = s.length() - (p.length() - pe);



	        if (ps == -1) {
            return equal(s, p);
        }
        if (pre > rear + 1) {
            return false;
        }
        if (!equal(s.substring(0, pre), p.substring(0, pre))
                || !equal(s.substring(rear + 1, s.length()), p.substring(pe + 1, p.length()))) {
            return false;
        }



	        for (int k = ps + 1; k < pe;) {
            //去掉多余的‘*’号
            while (k < pe && p.charAt(k) == '*') {
                ps = k;
                k++;
            }
            if (k == pe) return true;
            while (k < pe && p.charAt(k) != '*') k++;
            pre = indexOf(s, p.substring(ps + 1, k), pre);
            if (pre == -1) {
                return false;
            }
            pre += k - ps - 1;
            if (pre > rear + 1) {
                return false;
            }
            ps = k;
        }



	        return true;
    }
}

发表于 2018-05-07 21:06:28 回复(0)

C/C++

nbgao

class Solution {
public:
    bool isMatch(const char *s, const char *p) {
        int m = strlen(s);
        int n = strlen(p);
        if((s==NULL && p==NULL) || (m==0 && n==0))
            return true;
        if(m!=0 && n==0)
            return false;
        bool dp[m+1][n+1];
        memset(dp,false,sizeof(dp));
        dp[0][0] = true;
        for(int i=1;i<=n;i++)
        {
            if(p[i-1] == '*')
                dp[0][i] = dp[0][i-1];         }         for(int i=1;i<=m;i++)         {             for(int j=1;j<=n;j++)             {                 if(s[i-1] == p[j-1] || p[j-1]=='?')                     dp[i][j] = dp[i-1][j-1];                 if(p[j-1] == '*')                     dp[i][j] = dp[i][j-1] || dp[i-1][j];             }         }         return dp[m][n];
    }
};

发表于 2017-09-24 03:04:13 回复(0)

C/C++

Dancer_Wu

拜读 (@phexus)一种回溯的解法，很不错的

起初有一个问题总是搞不懂——回溯的时候总是记录最新的*，那么之前的*是否就不需要回溯呢？

这个问题其实是不需要再回溯的，在遇到最新的‘*’之前的序列是已经被确认匹配的，如果最终的结果能够匹配，那么区别只是每一个*所代替的序列的情况不同，例如ababc;*ab*。因此只需要记录最新的*的位置就可以了

编辑于 2020-04-11 13:58:50 回复(0)

phexus

直接用递归会超时，这里用到了回溯的思想。

'?' 比较好处理，++i，++j 即可

关键是 '*' ，这里定义了 i 和 j 的回溯点:
每当遇到 '*' 时，
记录 i 的回溯点 i_recall = i;
记录 j 的回溯点 j_recall = ++j，这里选择 j 自增后的位置，因为此时 j 为 '*'，尝试用后面的模式来匹配该元素。

当遇到不能匹配的点时，就会进入到第 3 个 if，此时把 i 回溯到 i_recall 后，同时 i_recall 自增，j 回溯到 j_recall，表示将原来记录的回溯点用 '*' 来匹配，再重新做这一轮的匹配。

最后要把末尾的 '*' 都忽略，若 p[j] 为空则代表匹配完成，若还有剩余元素说明不匹配。

下面的例子用了C++ STL 的 string 来表示:

class Solution {
public:
    bool isMatch(string s, string p) {
        int i = 0, j = 0, j_recall = 0, i_recall = 0;
        while (s[i]) {
            if (p[j] == '?' || s[i] == p[j]) {++i; ++j; continue;}
            if (p[j] == '*') {i_recall = i; j_recall = ++j; continue;}
            if (j_recall) {i = ++i_recall; j = j_recall; continue;}          
            return false;
        }
        while (p[j] == '*') ++j;
        return !p[j];
    }
};

编辑于 2018-02-09 15:35:45 回复(7)

戴浩男

/*
 *  思路：刚开始直接递归超时，改用dp通过
 *	状态定义：dp[i][j]表示s[0~i-1]是否匹配p[0~j-1]
 *	递推关系式：
 *	1.dp[i][j] = dp[i-1][j-1].   如果p[j-1]=='?' 或 s[i-1] == p[j-1]
 *	2.dp[i][j] = dp[i-1][j] || dp[i][j-1].  dp[i-1][j]表示保留p中的*，可以匹配s中跟多字符,dp[i][j-1]表示p中的*匹配空字符
 *  初始状态：s="", p=""应该返回true, s="", p="*"应该返回true, 其他初始状态如：s="", p="ab*"应该返回false
 */
public class Solution {
    public boolean isMatch(String s, String p) {
        //删除连续多个*，只保留一个*
    	p = removeduplicate(p);
        
    	int ls = s.length() + 1;
    	int lp = p.length() + 1;
    	//状态定义：dp[i][j]表示s[0~i-1]是否匹配p[0~j-1]
    	boolean[][] dp = new boolean[ls][lp];
        //初始状态：s="", p=""应该返回true
    	dp[0][0] = true;

        //初始状态：s="", p="*"应该返回true
    	if (p.length() > 0 && p.charAt(0) == '*')
    		dp[0][1] = true;
        
        //其他初始状态如：s="", p="ab*"应该返回false
    	
        //递推关系式：
        //1.dp[i][j] = dp[i-1][j-1].   如果p[j-1]=='?' 或 s[i-1] == p[j-1]
        //2.dp[i][j] = dp[i-1][j] || dp[i][j-1].  dp[i-1][j]表示保留p中的*，可以匹配s中跟多字符,
        //dp[i][j-1]表示p中的*匹配空字符
    	for (int i = 1; i < ls; i++) {
    		for (int j = 1; j < lp; j++) {
    			if (p.charAt(j-1) == '?' || (p.charAt(j-1) == s.charAt(i-1))) {
    				dp[i][j] = dp[i-1][j-1];
    			}
    			if (p.charAt(j-1) == '*') {
    				if (i == 1 && j == 1)
    					dp[i][j] = true;
    				else {
    					dp[i][j] = dp[i-1][j] || dp[i][j-1];
    				}
    			}
    		}
    	}
    	
    	
    	return dp[ls-1][lp-1];
    	
    }
    //删除连续重复的*，只保留一个*
    public String removeduplicate(String p) {
    	boolean last = false;
    	StringBuilder sb = new StringBuilder();
    	for (int i = 0; i < p.length(); i++) {
    		char c = p.charAt(i);
    		if (c != '*') {
    			sb.append(c);
    			last = false;
    		} else {
    			if (!last) {
    				sb.append(c);
    				last = true;
    			} else {
    				continue;
    			}
    		}
    	}
    	return sb.toString();
    }
}

发表于 2016-09-19 08:44:39 回复(0)

牛客2024007号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @param p string字符串 
     * @return bool布尔型
     */
    public boolean isMatch (String s, String p) {
        // write code here
        int lens = s.length();
        int lenp = p.length();
        boolean[][] dp = new boolean[lens + 1][lenp + 1];
        // dp[i][j] -> 如果 s.charAt(i) == s.charAt(j) -> dp[i][j] = dp[i - 1][j - 1]
        // s.charAt(j) == '?' dp[i][j] = dp[i - 1][j - 1]
        // s.charAt(j) == '*' dp[i][j] = dp[i - 1][j] || dp[i - 1][j - 1] || dp[i][j - 1]
        // 其他都是false
        dp[0][0] = true;
        for(int i = 1; i <= lenp; i++) {
            if(p.charAt(i - 1) == '*') dp[0][i] = dp[0][i - 1];
        }
        
        for(int j = 1; j <= lenp; j++) {
            for(int i = 1; i <= lens; i++) {
                if(s.charAt(i - 1) == p.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if(p.charAt(j - 1) == '?') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if(p.charAt(j - 1) == '*') {
                    dp[i][j] = (dp[i - 1][j] || dp[i - 1][j - 1] || dp[i][j - 1]);
                }
            }
        }
        return dp[lens][lenp];
    }
}

分类讨论的dp

编辑于 2024-02-02 23:48:03 回复(0)

C++

Mad_Cosma

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(), n = p.size();
        vector<vector<bool>> dp(m+1, vector<bool>(n+1, false));
        dp[0][0] = true;
        for (int i = 1; i <= n; i++) {
            if (p[i-1] == '*') dp[0][i] = dp[0][i-1];
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (p[j-1] != '*') {
                    dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '?');
                } else {
                    dp[i][j] = dp[i-1][j] || dp[i][j-1];
                }
            }
        }
        return dp[m][n];
    }
};

发表于 2023-03-22 16:49:15 回复(0)

C++

虚戈戈

分享解题思路，递归：

class Solution {
  public:
    bool _isMatch(const char* s, const char* p) {
        if (!p[0])return s[0] == 0;
        else if (p[0] == '*')
        {
            int i=0;
            while(p[i]=='*')i++;//没有这一行就会超时。。
            return _isMatch(s, p + i) || (s[0] != 0 && _isMatch(s + 1, p + i - 1));
        }
        else return (p[0] == s[0] || p[0] == '?') && _isMatch(s + 1, p + 1);
    }
    bool isMatch(string s, string p) {
        return _isMatch(s.c_str(), p.c_str());
    }
};

发表于 2023-02-28 13:59:31 回复(0)

刀马任平生

非得用char *😓

发表于 2022-05-23 10:23:52 回复(0)

Java

シkid~

public class Solution {
    public boolean isMatch(String s, String p) {
        // 动态规划：需要O(s.length()*p.length())的额外数组空间
        int lenS = s.length();
        int lenP = p.length();
        boolean[][] dp = new boolean[lenS+1][lenP+1];        // dp[i][j]表示s的前i个字符串和p的前j个字符串是否匹配
        dp[0][0] = true;
        // 初始化base case
        // dp[i][0]一定为false，无需初始化（i>0）
        // 如果p.substring(0,j)中只包含*，那么dp[0][j]为true
        for(int j=1; j<=lenP; j++) {
            if (p.charAt(j-1) == '*') {
                dp[0][j] = dp[0][j-1];
            } else {
                dp[0][j] = false;
            }
        }
        for(int i=1; i<=lenS; i++) {
            for(int j=1; j<=lenP; j++) {
                char charP = p.charAt(j-1);
                char charS = s.charAt(i-1);
                if (charP == charS || charP == '?') { // 如果p[j]是非通配符，那么s[i]必须为相同字母，并且dp[i][j]取决于dp[i-1][j-1]
                    dp[i][j] = dp[i-1][j-1];
                } else if (charP == '*') { // 如果p[j]是*，那么dp[i][j]的状态等于dp[i-1][j]或不考虑*：dp[i][j-1]
                    dp[i][j] = dp[i-1][j] | dp[i][j-1];
                }
            }
        }
        return dp[lenS][lenP];
    }
}

public class Solution {
    public boolean isMatch(String s, String p) {
        // 贪心+回溯+双指针，只需O(1)的空间
        // 贪心体现在哪?：能进行字符匹配，就绝不用*匹配，并且*尽量匹配少的字符(0~n)。这样的贪心可以保证每一种可能的匹配方式都考虑到
        int i = 0;      // s的移动指针
        int j = 0;      // p的移动指针
        int pi = -1;    // s处理通配符*的回溯指针
        int pj = -1;    // p处理通配符*的回溯指针
        int lenS = s.length();
        int lenP = p.length();
        while(i < lenS) {
            if (j<lenP && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) { // 如果是字符匹配 或是 ?匹配，则指针后移，无需考虑回溯指针
                i++;
                j++;
            } else if (j < lenP && p.charAt(j) == '*') { // 如果是*匹配，则指针仍然后移，但此时需要标记回溯指针。如果后续发现*匹配的字符数少了，需要通过回溯指针回溯处理
                pi = i;        // 注意此时i指针不后移，因为*可以匹配0~n个字符；如果i后移了，则表示*无法匹配0个字符
                pj = j++;
            } else if (pi >= 0) { // 此时发现匹配不上或者p字符串已经处理完，则考虑通过回溯指针回溯，从而使得p中的通配符*多匹配一些字符
                i = ++pi;        // 让p中的*通配符在s中多匹配一个字符
                j = pj+1;        // j回到p中*通配符的下一个字符
            } else { // 如果既无法匹配，又无法回溯，那么匹配失败
                return false;
            }
        }
        // 如果s字符串处理完，但p还未处理完
        for(; j<lenP; j++) {
            if (p.charAt(j) != '*') {
                return false;
            }
        }
        return true;
    }
}

发表于 2022-02-26 10:40:33 回复(0)

Java

玄鉴

class Solution {
    public boolean isMatch(String s, String p) {
        int m=s.length();
        int n=p.length();
        boolean[][]dp=new boolean[m+1][n+1];
        dp[0][0]=true;
        for(int i=0;i<n;i++){
            if(p.charAt(i)=='*') dp[0][i+1]=true;
            else break;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(Character.isLetter(p.charAt(j-1))){
                    dp[i][j]= ((s.charAt(i-1)==p.charAt(j-1)&&dp[i-1][j-1]));
                }else if(p.charAt(j-1)=='?'){
                    //可以匹配一个
                    dp[i][j]=dp[i-1][j-1];

                }else{
                    //当为*
                    for(int k=0;k<=m;k++){
                        if(dp[k][j-1]){
                            dp[i][j]=true;
                            break;
                        }
                    }
                }
            }
        }
        return dp[m][n];
    }
}

发表于 2022-01-01 21:19:57 回复(0)

Python3

Andronie

投机取巧🤭

class Solution:
    def isMatch(self , s: str, p: str) -> bool:
        # write code here
        import re
        r = re.findall('\*\*+', p)
        for i in r:
            p = p.replace(i, "*")
        p = p.replace("?", ".")
        p = p.replace("*", ".*")
        res = re.findall(p, s)
        if s in res:
            return True
        return False

发表于 2021-12-29 14:56:00 回复(0)

通配符匹配

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题