首页 > 试题广场 >

字符串通配

[编程题]字符串通配

热度指数：4184 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

对于字符串A，其中绝对不含有字符’.’和’*’。再给定字符串B，其中可以含有’.’或’*’，’*’字符不能是B的首字符，并且任意两个’*’字符不相邻。exp中的’.’代表任何一个字符，B中的’*’表示’*’的前一个字符可以有0个或者多个。请写一个函数，判断A是否能被B匹配。

给定两个字符串A和B,同时给定两个串的长度lena和lenb，请返回一个bool值代表能否匹配。保证两串的长度均小于等于300。

测试样例：

"abcd",4,".*",2

返回：true

算法知识视频讲解

Alex-大伟

package alex.suda.dp;

import java.util.Scanner;

public class test8 {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNext()) {
			int n = scanner.nextInt();
			String A = scanner.next();
			int m = scanner.nextInt();
			String B = scanner.next();
			System.out.println(chkWildMatch(A, n, B, m));
		}
	}

	public static boolean chkWildMatch(String A, int lena, String B, int lenb) {
		// d[i][j]表示A中的1~i位可以匹配B中的1~j位
		boolean[][] d = new boolean[lena + 1][lenb + 1];
		// 初始化
		d[0][0] = true;
		for (int i = 1; i <= lena; i++) {
			for (int j = 1; j <= lenb; j++) {
				if (B.charAt(j - 1) == '*') {
					d[i][j] = d[i - 1][j] || d[i][j - 1];
				} else if (B.charAt(j - 1) == '.') {
					d[i][j] = d[i - 1][j - 1];
				} else {
					d[i][j] = d[i - 1][j - 1] && A.charAt(i - 1) == B.charAt(j - 1);
				}
			}
		}
		return d[lena][lenb];
	}
}

发表于 2016-10-08 20:05:58 回复(8)

更多回答

Python

华科平凡

python解法，使用re模块：

import re
class WildMatch:
    def chkWildMatch(self, A, lena, B, lenb):
        def fullmatch(regex, string, flags=0):
            return re.match("(?:" + regex + r")\Z", string, flags=flags)
        if fullmatch(B,A):
            return True
        return False

编辑于 2017-09-12 14:18:46 回复(1)

luuuyi

排前面几名的都是什么鬼，这个题要做的是正则匹配，不是字符串通配符匹配

//正则匹配题目，注意和通配符匹配题目区别开来

class WildMatch {

public:

bool chkWildMatch(string A, int lena, string B, int lenb) {

// write code here

vector < vector < bool >> dp(lena + 1 , vector < bool > (lenb + 1 , false ));

//初始化第一位和第一行的dp值

dp[ 0 ][ 0 ] = true ;

for ( int i = 1 ;i <= lenb;i ++ ){

if (B[i - 1 ] == '*' ) dp[ 0 ][i] = dp[ 0 ][i - 2 ];

}

//状态转移方程实现

for ( int i = 1 ;i <= lena;i ++ ){

for ( int j = 1 ;j <= lenb;j ++ ){

//当前pattern为.或者对等字符时，对应的dp值为左上角的dp值

if (B[j - 1 ] == '.' || B[j - 1 ] == A[i - 1 ]){

dp[i][j] = dp[i - 1 ][j - 1 ];

}

else if (B[j - 1 ] == '*' ){

//当pattern为*的时候考虑两种情况

//*表达为0，那就是取dp[i][j-2]的值，不需要解释

//*表达为除了0外的任何值，前提是*之前的字符与当前待匹配的字符能够匹配

//dp值为dp[i-1][j]

dp[i][j] = (dp[i][j - 2 ]) || ((A[i - 1 ] == B[j - 2 ] || B[j - 2 ] == '.' ) && dp[i - 1 ][j]);

}

else {

dp[i][j] = false ;

}

return dp[lena][lenb];

}

};

编辑于 2017-06-08 13:28:40 回复(1)

Java

詆調壹點

import java.util.*;
public class WildMatch {
    public boolean chkWildMatch(String A, int lena, String B, int lenb) {
		boolean[][] dp = new boolean[lena + 1][lenb + 1];
		dp[0][0] = true;
		for (int i = 1; i <= lena; i ++ ) {
			for (int j = 1; j <= lenb; j ++ ) {
				if(B.charAt(j - 1) == '.' || B.charAt(j - 1) == A.charAt(i - 1)) dp[i][j] = dp[i - 1][j - 1];
				if(B.charAt(j - 1) == '*') dp[i][j] = dp[i - 1][j] || dp[i][j - 1];
			}
		}
		return dp[lena][lenb];
	}
}

发表于 2016-10-18 11:37:47 回复(0)

SPACELAN

class WildMatch {
public:
	bool chkWildMatch(string A, int lena, string B, int lenb) {
		if (B[0] == '*')
			return false;
		vector<vector<bool> > dp(lenb + 1, vector<bool>(lena + 1, false));
		dp[0][0] = true;
		for (int i = 0; i < lenb; i++) {
			if (B[i] == '*') {
				dp[i + 1][0] = dp[i - 1][0];
				for (int j = 0; j < lena; j++) {
					dp[i + 1][j + 1] = dp[i][j + 1] || dp[i - 1][j + 1];
					if (isEqual(A[j], B[i - 1]))
						dp[i + 1][j + 1] = dp[i + 1][j + 1] || dp[i + 1][j];
				}
			}
			else {
				for (int j = 0; j < lena; j++) {
					if (isEqual(A[j], B[i])) {
						dp[i + 1][j + 1] = dp[i][j];
					}
				}
			}
		}
		return dp[lenb][lena];
	}
	inline bool isEqual(char a, char b) {
		if (a == b || b == '.')
			return true;
		else
			return false;
	}
};

发表于 2015-08-06 14:22:21 回复(3)

风雨夜人

class WildMatch {
public:
    bool chkWildMatch(string A, int lena, string B, int lenb) {
        // write code here
        int i=lena-1;
        int j=lenb-1;
        while(i>=0&&j>=0){
            if(A[i]==B[j]||B[j]=='.'){
                i--;
                j--;
            }
            else if(B[j]=='*'){
                lenb=j;
                j--;
            }
            else {
                i=i-j+lenb-2;
                j=lenb-1;
            }
        }
        if(j<0)
            return 1;
        else
            return 0;
    
    }
    
};

该题只要从后往前匹配就可以了，遇到‘.‘跳过，遇到’*‘分段。

发表于 2016-05-21 16:45:31 回复(9)

Java

啦啦啦～～

//递归详解
import java.util.*;

public class WildMatch {
    public boolean chkWildMatch(String A, int lena, String B, int lenb) {
        // write code here

        return isP(A,0,B,0);
    }
    //ia为A当前索引位置，ib为B当前索引位置,函数返回值为到当前位置是否匹配
    //结束且结果为true或false
    public  boolean isP(String A,int ia,String B,int ib){
        //当A匹配结束且B结束返回true
        if(ia==A.length()&&ib==B.length())
            return true;
        //边界控制,超出返回false
        if(ib>=B.length()||ia>=A.length())
            return false;
        //当A匹配结束但B还没匹配到结尾返回false
        if((ia==A.length()&&ib!=B.length()))
            return false;

        //当A[ia]!=B[ib]且B[ib]!='.'时返回false
        if(A.charAt(ia)!=B.charAt(ib)&&B.charAt(ib)!='.')
            return false;


        boolean isp = false;

        //B的ib下一个是*时
        if((ib+1<B.length())&&B.charAt(ib+1)=='*'){
            //选用*的功能，ib索引位置不变，ia+1进行匹配
            boolean is1 = isP(A,ia+1,B,ib);
            //不选用*的功能,ib跳到'*'后一个位置ib+2，ia+1进行匹配
            boolean is2 = isP(A,ia+1,B,ib+2);

            isp = is1|is2;
        }else{//下一个不是*时，直接进行下一个匹配

            isp = isP(A,ia+1,B,ib+1);
        }

        return isp;
    }


}

发表于 2017-07-27 03:59:58 回复(0)

夕一啊

//递归有点多啊，不断调用自己往后匹配

class WildMatch {
public:
//flag 是看匹配了几次，因为只能匹配0或多次，不能1次
//nowa 是a匹配到哪一位了， nowb 是b匹配到哪一位了， b匹配完就结束
   bool match(string A, int lena,int nowa, string B, int lenb,int nowb,int flag){
    	if(nowa <= lena && nowb == lenb) return true;
        if( nowa > lena || nowb > lenb ) return false;
        if(B[nowb] == '.'){
            if(B[nowb+1] == '*'){
                if(flag == 1){
                    //若之前匹配了一次，必须再匹配
                    return match(A,lena,nowa+1,B,lenb,nowb,flag+1) ;
                }
                else
                    //匹配多一次，最后一次匹配，或匹配0次 
                    return match(A,lena,nowa+1,B,lenb,nowb,flag+1) || match(A,lena,nowa,B,lenb,nowb+2,0) || match(A,lena,nowa+1,B,lenb,nowb+2,0) ;// 匹配多次 || 匹配0次 
             }
             else
                return  match(A,lena,nowa+1,B,lenb,nowb+1,0);
        }
        else if( A[nowa] != B[nowb])
            return false;
        else if(  A[nowa] == B[nowb]) {
        //情况和“.”一样
            if(B[nowb+1] == '*'){
                if(flag == 1){
                    return match(A,lena,nowa+1,B,lenb,nowb,flag+1);
                }
                else
                    return match(A,lena,nowa+1,B,lenb,nowb,flag+1) || match(A,lena,nowa,B,lenb,nowb+2,0)  || match(A,lena,nowa+1,B,lenb,nowb+2,0) ;// 匹配多次 || 匹配0次
            }
            else
                return  match(A,lena,nowa+1,B,lenb,nowb+1,0);               
        }
       return false;
   }
    bool chkWildMatch(string A, int lena, string B, int lenb) {
        // write code here
        return match(A,lena,0,B,lenb,0,0);
    }
};

编辑于 2017-05-31 17:12:32 回复(0)

C/C++

Er_myy

看了上边好多代码都是有bug，可以测试样例：
样例一：
    "" ， 0， ".*"， 2 
    应该输出true，绝多数代码输出false
样例二：
    "aaaaabcd", 8, "a*abcd" 
    应该输出true

class WildMatch {
public:
    bool chkWildMatch(string A, int lena, string B, int lenb) {
        // write code here
        int **dp=new int*[lena+1];
        for(int i=0; i<=lena; ++i) dp[i]=new int[lenb+1];
        dp[0][0]=true;
        for(int i=1; i<=lena; ++i) dp[i][0]=false;
        for(int i=1; i<=lenb; ++i) dp[0][i]=(i>=2 && B[i-1]=='*' && dp[0][i-2]);
        for(int i=1; i<=lena; ++i)
            for(int j=1; j<=lenb; ++j){
                int ii=i-1;
                int jj=j-1;
                if(B[jj]=='*')
                dp[i][j]=dp[i][j-2] || 
                    ((dp[i-1][j] || (dp[i-1][j-2])&&(B[jj-1]=='.' || B[jj-1]==A[ii]));
                else if(B[jj]=='.')
               	dp[i][j]=dp[i-1][j-1];
                else 
                dp[i][j]=dp[i-1][j-1] && A[ii]==B[jj];
            }
        int ans=dp[lena][lenb];
        for(int i=0; i<=lena; ++i) delete []dp[i];
        delete []dp;
        return ans;
    }
};

编辑于 2017-06-16 07:46:43 回复(5)

Scheaven

/*
 *@author snow 
 *@time 2016-08-13 16:16:28
 * *学java的，题比较简单，所以第一次尝试用C++写程序 
 *算法复杂度O(n);姑且认为n=max(lena,lenb);
*/
class WildMatch {
public:
    bool chkWildMatch(string A, int lena, string B, int lenb) {
        // write code here
        if(B.find(".*")<B.length()){
            return true;
        }
		int j = 0;
		for(int i=0;i<lenb;i++){
			if(j>=lena){
				return true;
			}
			if(A[j] == B[i] || B[i] == '.'){
				j++;
			}else if(B[i] == '*'){
				if(A[j] == B[i-1]){
					j++;
					i--;
				}else if(A[j] == B[i+1]){
					j++;
					i++;
				}
			}
		}
		if(j>=lena){
			return true;
		}else
	 		return false;
    }
};

编辑于 2016-08-13 16:27:04 回复(3)

你快乐吗

投机取巧了

import java.util.regex.Pattern;
public class WildMatch {
    public boolean chkWildMatch(String A, int lena, String B, int lenb) {
        // write code here
        return Pattern.matches(B, A);
    }
}

发表于 2020-12-20 18:30:56 回复(0)

C/C++

哦哦哦5

class WildMatch {
public:
    bool chkWildMatch(string A, int lena, string B, int lenb) {
        // write code here
        int count = 0;
        B += " ";
        for(int i = 1; i <= lenb; i++)
        {
            if(B[i-1] != '*')
            {
                if(B[i] == '*')//处理 字母+*情况
                {
                    for(int j = 0; j < lena; j++)
                    {
                        if(B[i-1] == '.')
                            return true;
                        if(B[i-1] == A[j])
                            count++;
                    }
                }
                else//处理 只有单次字母情况
                {
                    for(int j = 0; j < lena; j++)
                    {
                        if(B[i-1] == A[j])
                        {
                            count++;
                            break;
                        }
                    }
                }
            }
        }
        return count >= lena;
    }
};

发表于 2018-08-04 16:09:00 回复(0)

Erice

我就是想问问笔试的时候能这样写吗？？？
public boolean chkWildMatch(String A, int lena, String B, int lenb) {
        // write code here
        return Pattern.matches(B,A);
    }

发表于 2018-04-26 10:05:08 回复(2)

C/C++

nbgao

class WildMatch {
public:
    bool chkWildMatch(string A, int lena, string B, int lenb) {
        if(B[0]=='*')
            return false;
        vector<vector<bool> > dp(lenb+1, vector<bool>(lena+1,false));
        dp[0][0] = true;
        for(int i=0;i<lenb;i++)
        {
            if(B[i] == '*')
            {
                dp[i+1][0] = dp[i-1][0];
                for(int j=0;j<lena;j++)
                {
                    dp[i+1][j+1] = dp[i][j+1] || dp[i-1][j+1];
                    if(A[j]==B[i-1] || B[i-1]=='.')
                        dp[i+1][j+1] = dp[i+1][j+1] || dp[i+1][j];                 }             }else{                 for(int j=0;j<lena;j++)                     if(A[j]==B[i] || B[i]=='.')                         dp[i+1][j+1] = dp[i][j];             }         }         return dp[lenb][lena];
    }
};

发表于 2017-10-12 01:16:45 回复(0)

kelele67

//检查正则表达式的匹配
//递归
class WildMatch {
public:
    bool chkWildMatch(string A, int lena, string B, int lenb) {
        // write code here
        return isMatch(A.c_str(), B.c_str());
    }

private:
	bool isMatch(const char *a, const char *b) {
		if (*b == '\0') return *a == '\0';
		//如果字母b后面不是'*'，那么b必须匹配一个，否则FALSE
		if (*(b + 1) != '*') {
			// 注意：虽然b为'.'时代表任意一个字符，但是不能匹配 '\0'
			if (*a == *b || *b == '.' && *a != '\0') {
				return isMatch(a + 1, b + 1);
			} else {
				return false;
			}
		} else {
			//字母b后面是'*''
			//当字母b匹配或者b为'.'时，跳过b和'*'再进行匹配
			while (*a == *b || (*b == '.' && *a != '\0')) {
				if (isMatch(a, b + 2)) {
					return true;
				}
				a++;
			}
			return isMatch(a, b + 2);
		}
	}
};

发表于 2017-04-10 22:13:39 回复(0)

Java

牛客482605号

import java.util.*;

public class WildMatch {

public static boolean chkWildMatch(String A, int lena, String B, int lenb) {

boolean result[][] = new boolean[lena+1][lenb+1];

result[0][0] = true;

for (int i = 1; i < lena+1; i++) {

for (int j = 1; j < lenb+1; j++) {

if(B.charAt(j-1) == '.'){

result[i][j] = result[i-1][j-1];

}else if(B.charAt(j-1) == '*'){

if(A.charAt(i-1)==B.charAt(j-2) || B.charAt(j-2) == '.'){

result[i][j] = result[i-1][j] || result[i][j-1];

}else{ //***当遇到*时，若A前一位无法表示B当前位，则不应再继续比较，例如ab和a*，若前一位无法表示B当前位则必然匹配失败。否则会继续向上搜索a与a*匹配产生错误结果。题目中要求*只能指代前一位出现的结果。

result[i][j] = false;

}

}else{

result[i][j] = result[i-1][j-1] && B.charAt(j-1) == A.charAt(i-1);

}

return result[lena][lenb];

}

发表于 2017-03-28 16:44:47 回复(0)

Echo001

 bool chkWildMatch(string A, int lena, string B, int lenb) {
      	//设置初始值	
        bool** temp = new bool*[lenb + 1];
        for (int i=0; i<lenb+1; i++)
        {
            temp[i] = new bool[lena + 1];
            temp[i][0] = false;
        }
        for (int i=0; i<lena+1; i++)
        {
            temp[0][i] = false;
        }
        temp[0][0] = true;
        /*
            *号：d[i][j]=d[i][j-1] || d[i-1][j]
          非*号：d[i][j]=d[i-1][j-1] && m(i,j)
          其中：m(i,j) = (b[i]== '.' || b[i]==a[i])
        */
        for (int i=1; i<=lenb; i++)
        {
            if(B.at(i-1) == '*'){
                for (int j=1; j<=lena; j++){
                    temp[i][j] = temp[i][j-1] || temp[i-1][j];
                }
            }else{
                for (int j=1; j<=lena; j++)
                {
                    temp[i][j] = temp[i-1][j-1] && (B.at(i-1) == '.' || A.at(j-1) == B.at(i-1));
                }
            }
        }

        return temp[lenb][lena];
    }

发表于 2016-07-17 21:46:58 回复(1)

chenyu

class WildMatch {
public:
	bool chkWildMatch(string A, int lena, string B, int lenb) {
		const char * p1 = A.c_str();
		const char * p2 = B.c_str();
		return match(p2, p1);
		
	}

	int matchstar(int c,const char *regexp,const char *text) {
		do {// a * matches zero or more instances
			if (matchhere(regexp, text)) return 1;
		} while (*text != '\0' && (*text++ == c || c == '.'));
		return 0;
	}
	int matchhere( const char *regexp, const char *text) {
		if (regexp[0] == '\0') return 1;
		if (regexp[1] == '*') return matchstar(regexp[0], regexp + 2, text);
		if (regexp[0] == '$' && regexp[1] == '\0') return *text == '\0';
		if (*text != '\0' && (regexp[0] == '.' || regexp[0] == *text)) return matchhere(regexp + 1, text + 1);
		return 0;
	}

	int match(const char *regexp,const char *text) {
		if (regexp[0] == '^') return matchhere(regexp + 1, text);
		do {// must look even if string is empty
			if (matchhere(regexp, text)) return 1;
		} while (*text++ != '\0');
		return 0;
	}
};

发表于 2016-05-26 20:25:27 回复(0)

吐蕃国师大轮明王鸠摩智

import java.util.*;

public class WildMatch {
    public boolean chkWildMatch(String A, int lena, String B, int lenb) {
        // write code here
        char[] SA=A.toCharArray();
        char[] SB=B.toCharArray();
        return chkWildMatchHelper(SA,0,SB,0);
    }
    
    public boolean chkWildMatchHelper(char[] SA,int ai,char[] SB,int bi){
        if(bi==SB.length)
            return ai==SA.length;
        if(bi+1==SB.length || SB[bi+1]!='*'){
            if(ai!=SA.length && (SA[ai]==SB[bi] || SB[bi]=='.'))
                return chkWildMatchHelper(SA,ai+1,SB,bi+1);
            else
                return false;
        }
        else{
            while(ai!=SA.length && (SA[ai]==SB[bi] || SB[bi]=='.')){
                if(chkWildMatchHelper(SA,ai,SB,bi+2))
                    return true;
                ai++;
            }
            return chkWildMatchHelper(SA,ai,SB,bi+2);
        }
    }
}

发表于 2016-04-07 19:04:05 回复(0)

Java

烂泥湾

public class WildMatch {
    public boolean chkWildMatch(String A, int lena, String B, int lenb) {
        return A.matches(B);
    }
}

发表于 2016-07-16 00:01:51 回复(0)

提交观点

问题信息

动态规划

来自：面试常考算法题(十)-...

难度：

57条回答 108收藏 14165浏览

通过挑战的用户

查看代码

前端学习中

2022-08-27 18:43:32
MC枫少

2022-06-16 15:44:12
大龄程序缘

2022-06-07 12:42:13
up淋雨

2022-04-27 19:20:31
牛客88709...

2022-04-15 16:00:55

字符串通配

问题信息

热门推荐

通过挑战的用户

相关试题