首页 > 试题广场 >

字符串匹配问题

[编程题]字符串匹配问题

热度指数：2486 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

对于字符串str，其中绝对不含有字符’.’和‘*’。再给定字符串exp，其中可以含有’.’或’‘*’，’*’字符不能是exp的首字符，并且任意两个’*‘字符不相邻。exp中的’.’代表任何一个字符，exp中的’*’表示’*‘的前一个字符可以有0个或者多个。请写一个函数，判断str是否能被exp匹配(注意：输入的数据不保证合法，但只含小写字母和‘.’和‘*’)。

输入描述:

输入包含两行，两个字符串，分别代表str和exp。

输出描述:

如果str是能被exp匹配，请输出“YES”，否则输出“NO”。

示例1

输入

abc
abc

输出

YES

示例2

输入

abcd
.*

输出

YES

备注:

时间复杂度,额外空间复杂度,(n为字符串str长度，m为字符串exp长度)

算法知识视频讲解

helloxuanbao

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>

// 初始化一个动态大小的矩阵
#define INIT_MATRIX(TYPE, PTR, COL, ROW) \
    (PTR) = (TYPE **) malloc(sizeof(TYPE *) * (COL));\
    for (int i = 0; i < (COL); i++)\
        (PTR)[i] = (TYPE *) calloc((ROW), sizeof(TYPE))

// 释放一个动态大小的矩阵
#define FREE_MATRIX(PTR, COL) \
    for (int i = 0; i < (COL); i++) {\
        free((PTR)[i]);\
    }\
    free((PTR))
#define MAXLEN 301

bool is_valid(char *str, char *exp);

bool **get_dp(const char *str, const char *exp, int str_len, int exp_len);

int main(void) {
    char str[MAXLEN], exp[MAXLEN];
    scanf("%s%s", str, exp);
    if (!is_valid(str, exp)) {
        printf("NO\n");
        return 0;
    }
    int str_len = (int) strlen(str);
    int exp_len = (int) strlen(exp);
    bool **dp = get_dp(str, exp, str_len, exp_len);
    for (int i = str_len - 1; i >= 0; i--) {
        for (int j = exp_len - 2; j >= 0; j--) {
            if (exp[j + 1] != '*') {
                dp[i][j] = (exp[j] == '.' || str[i] == exp[j])
                           && dp[i + 1][j + 1];
            } else {
                int si = i;
                while (si != str_len && (exp[j] == '.' || str[si] == exp[j])) {
                    if (dp[si][j + 2]) {
                        dp[i][j] = true;
                        break;
                    }
                    si++;
                }
                if (!dp[i][j]) {
                    dp[i][j] = dp[si][j + 2];
                }
            }
        }
    }
    printf("%s\n", dp[0][0] ? "YES" : "NO");
    FREE_MATRIX(dp, strlen(str));
    return 0;
}

bool is_valid(char *str, char *exp) {
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] == '.' || str[i] == '*') {
            return false;
        }
    }
    for (int i = 0; i < strlen(exp); i++) {
        if (str[i] == '*' && (i == 0 || str[i - 1] == '*')) {
            return false;
        }
    }
    return true;
}

bool **get_dp(const char *str, const char *exp, int str_len, int exp_len) {
    bool **dp;
    INIT_MATRIX(bool, dp, str_len + 1, exp_len + 1);
    dp[str_len][exp_len] = true;
    for (int j = exp_len - 2; j >= 0; j -= 2) {
        dp[str_len][j] = exp[j + 1] == '*';
        if (!dp[str_len][j]) {
            break;
        }
    }
    dp[str_len - 1][exp_len - 1] = exp[exp_len - 1] == '.' ||
                                   str[str_len - 1] == exp[exp_len - 1];
    return dp;
}

发表于 2022-02-12 14:24:46 回复(0)

Python

牛客157007370号

def buhefa(s):
if s[0]=='*':
return 1
for i in range(len(s)-1):
if s[i]=='*' and s[i+1]=='*':
return 1
return 0

def quchong(exp):
i=0
while i<len(exp)-2:
if exp[i+1]=='*' and exp[i]==exp[i+2]:
exp=exp[:i+2]+exp[i+3:]
else:
i+=1

def solve(s,exp):
flag=0
if buhefa(exp):
return 0
else:
i,j=0,0
while i<len(s) and j<len(exp):
if j<len(exp)-1 and exp[j+1]=='*':
if exp[j]=='.':
if j+2==len(exp):
break
else:
j+=2
while i<len(s) and s[i]!=exp[j]:
i+=1
i_bianli=i+1
while i_bianli<len(s):
if solve(s[i_bianli:],exp[j:]):
return 1
i_bianli+=1

else:
while i<len(s) and s[i]!=exp[j]:
i+=1
j+=2
else:
if exp[j]==s[i] or exp[j]=='.':
i+=1
j+=1
else:
return 0
flag=1
break
if flag==0:
return 1

s=input()
exp=input()
flag=solve(s,exp)
if flag:
print('YES')
else:
print('NO')

发表于 2020-03-20 10:19:38 回复(0)

Java

jahentao

递归解法

import java.util.*;

public class Main {

    //isValid
    public static boolean isValid(char[] s, char[] e) {
        for(int i = 1; i < e.length; i++) {
            if (e[i] == '*' && e[i - 1] == '*')
                return false;
        }
        return true;
    }

    public static boolean judge(char[] s, char[] e, int si, int ei) {
        if (ei == e.length) {
            return si == s.length;
        }
        if (ei + 1 == e.length || e[ei + 1] != '*') {
            return si != s.length && (e[ei] == s[si] || e[ei] == '.')
                && judge(s, e, si + 1, ei + 1);
        }
        while (si != s.length && (e[ei] == s[si] || e[ei] == '.')) {
            if (judge(s, e, si, ei + 2)) {
                return true;
            }
            si ++;
        }
        return judge(s, e, si, ei + 2);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] s = sc.nextLine().toCharArray();
        char[] e = sc.nextLine().toCharArray();
        sc.close();
        if (!isValid(s, e)) {
            System.out.println("NO");
            return;
        }
        if (!judge(s, e, 0, 0)) {
            System.out.println("NO");
        } else {
            System.out.println("YES");
        }
    }
}

动态规划解法

import java.util.*;
public class Main {
    public static boolean isValid(char[] s, char[] e) {
        for (int i = 0; i < s.length; i++) {
            if (s[i] == '*' || s[i] == '.') {
                return false;
            }
        }
        for (int i = 0; i < e.length; i++) {
            if (e[i] == '*' && (i == 0 || e[i - 1] == '*')) {
                return false;
            }
        }
        return true;
    }
    public static boolean isMatchDP(String str, String exp) {
        if (str == null || exp == null) {
            return false;
        }
        char[] s = str.toCharArray();
        char[] e = exp.toCharArray();
        if (!isValid(s, e)) {
            return false;
        }
        boolean[][] dp = initDPMap(s, e);
        for (int i = s.length - 1; i > -1; i--) {
            for (int j = e.length - 2; j > -1; j--) {
                if(e[j + 1] != '*') {
                    dp[i][j] = (s[i] == e[j] || e[j] == '.') && dp[i + 1][j + 1];
                } else {
                    int si = i;
                    while (si != s.length && (s[si] == e[j] || e[j] == '.')) {
                        if (dp[si][j + 2]) {
                            dp[i][j] = true;
                            break;
                        }
                        si++;
                    }
                    if (dp[i][j] != true) {
                        dp[i][j] = dp[si][j + 2];
                    }
                }
            }
        }
        return dp[0][0];
    }
    public static boolean[][] initDPMap(char[] s, char[] e) {
        int slen = s.length;
        int elen = e.length;
        boolean[][] dp = new boolean[slen + 1][elen + 1];
        dp[slen][elen] = true;
        for (int j = elen - 2; j > -1; j -= 2) {
            if (e[j] != '*' && e[j + 1] == '*') {
                dp[slen][j] = true;
            } else {
                break;
            }
        }
        if (slen > 0 && elen > 0) {
            if ((e[elen - 1] == '.' || s[slen - 1] == e[elen - 1])) {
                dp[slen - 1][elen - 1] = true;
            }
        }
        return dp;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        String exp = sc.nextLine();
        if (isMatchDP(str, exp)) {
            System.out.println("YES");
        } else {
            System.out.println("NO");
        }
    }
}

发表于 2020-05-25 10:26:54 回复(0)

牛客79631828号

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        String s1 = sc.nextLine();
        String s2 = sc.nextLine();
        if (isMatch(s1, s2))
            System.out.println("YES");
        else
            System.out.println("NO");
        sc.close();
    }
    
    public static boolean isValid(String s1, String s2) {
        if ((s1 == null && s2 != null) || (s1 != null && s2 == null))
            return false;
        if (s1 == null && s2 == null)
            return true;
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        for (int i = 0; i < str1.length; i++) {
            if (str1[i] == '*' || str1[i] == '.')
                return false;
        }
        for (int i = 0; i < str2.length; i++) {
            if (str2[i] == '*' && (i == 0 || str2[i-1] == '*'))
                return false;
        }
        return true;
    }
    
    public static boolean isMatch(String s1, String s2) {
        if (!isValid(s1, s2))
            return false;
        char[] str = s1.toCharArray();
        char[] exp = s2.toCharArray();
        return getDP(str, exp);
    }
    
    //str[si...slen]是否能被exp[ei...elen]匹配, 以exp以及ei为判断基准
    public static boolean process(char[] str, char[] exp, int si, int ei) {
        //当exp走完时，若si也走到头了，空只能匹配空
        if (ei == exp.length)
            return si == str.length;
        //要么遍历到exp最后一位，要么后面不是*
        if(ei == exp.length-1 || exp[ei+1] != '*') {
            //如果str都遍历完了自然false；如果当前位置不等或后续无法匹配，false
            return si != str.length
                && process(str, exp, si+1, ei+1) 
                && (str[si] == exp[ei] || exp[ei] == '.');
        }
        //此时exp肯定没到最后且ei+1位置为'*', 比如aaaaXXX与a*XXX, 只要能出来匹配成功一对，即可返回true
        while (si != str.length && (str[si] == exp[ei] || exp[ei] == '.')) {
            if (process(str, exp, si, ei+2))
                return true;
            si++;
        }
        //说明此时尽管exp[ei+1] == '*', 但当前str[si] 根本无法匹配出来 exp[ei]，那么
        //只能让exp[ei]已经'*'为空，继续往后查吧
        return process(str, exp, si, ei+2);
    }
    
    //动态规划
    public static boolean getDP(char[] str, char[] exp) {
        //dp[i][j]表示str从[i...len-1]与exp[j...len-1]是否可以匹配
        boolean[][] dp = new boolean[str.length+1][exp.length+1];
        dp[str.length][exp.length] = true;
        for (int i = exp.length-2; i > -1; i--) {
            if (exp[i] != '*' && exp[i+1] == '*')
                dp[str.length][i] = true;
            else
                break;
        }
        if (str.length > 0 && exp.length > 0)
            dp[str.length-1][exp.length-1] = exp[exp.length-1] == str[str.length-1]
                                        || exp[exp.length-1] == '.';
        for (int i = str.length-1; i > -1; i--) {
            for (int j = exp.length-2; j > -1; j--) {
                if (exp[j+1] != '*') {
                    dp[i][j] = (str[i] == exp[j] || exp[j] == '.') && dp[i+1][j+1];
                }
                else {
                    int si = i;
                    while (si < str.length && (str[si] == exp[j] || exp[j] == '.')) {
                        if (dp[si][j+2]) {
                            dp[i][j] = true;
                            break;
                        }
                        si++;
                    }
                    if(!dp[i][j])
                        dp[i][j] = dp[si][j+2];
                }
            }
        }
        return dp[0][0];
    }
}

发表于 2021-08-03 20:04:29 回复(0)

犯困的小山竹在找内推

运行时间：7ms
超过100.00%用Java提交的代码

占用内存：10824KB

超过89.32%用Java提交的代码

import java.io.*;

public class Main{
    
    public static void main(String[] args) throws IOException{
        BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
        String str = sc.readLine();
        String exp = sc.readLine();
        char[] ch1= str.toCharArray();
        char[] ch2 = exp.toCharArray();
        
        boolean result = isMatch(ch1,ch2);
        if(result){
            System.out.print("YES");
        }
        else{
            System.out.print("NO");
        }
    }
    
    public static boolean isValid(char[] ch1,char[] ch2){
        for(int i = 0;i<ch1.length;i++){
            if(ch1[i]=='.'||ch1[i]=='*'){
                return false;
            }
        }
        for(int i = 0; i< ch2.length;i++){
            if(ch2[i]=='*'&&(i==0||ch2[i-1]=='*')){
                return false;
            }
        }
        return true;
    }
    
    public static boolean isMatch(char[] s,char[] e){
        if(s==null||e==null){
            return false;
        }
        return isValid(s,e) ? process(s,e,0,0): false;
    }
    
    public static boolean process(char[] s, char[] e, int si ,int ei){
        if(ei==e.length){
            return s.length ==si;
        }
        if(ei+1==e.length||e[ei+1]!='*'){
            return   si!=s.length &&(s[si]==e[ei]||e[ei]=='.') && process(s,e,si+1,ei+1);
        }
        while(si!=s.length && (e[ei]==s[si]||e[ei]=='.')){
            if(process(s,e,si,ei+2)){
                return true;
            }
            si++;
        }
        return process(s,e,si,ei+2);

    }

}

发表于 2021-03-24 15:26:21 回复(0)

牛客777898126号

s,p = input(),input()
m, n = len(s), len(p)
dp = [[False]*n for _ in range(m)]
dp[0][0] = True
for i in range(m):
for j in range(1, n):
if i == 0:
dp[i][j] = j > 1 and p[j] == '*' and dp[i][j-2]
elif p[j] in [s[i], '.']:
dp[i][j] = dp[i-1][j-1]
elif p[j] == '*':
dp[i][j] = j > 1 and dp[i][j-2] or p[j-1] in [s[i], '.'] and dp[i-1][j]
else:
dp[i][j] = False
if dp[-1][-1]:
print("YES")
else:
print("NO")

发表于 2020-05-16 18:22:36 回复(0)

包子冲汤胡辣汤

#include<cstdio>
(802)#include<cstring>
#include<algorithm>
using namespace std;
char str1[310],str2[310];
int dp[310][310];
int main(){
    while(~scanf("%s %s",str1+1,str2+1)){
         fill(dp[0],dp[0]+310*310,0);
         int len1=strlen(str1+1);
         int len2=strlen(str2+1);
         int flag=0;
         for(int i=1;i<=len2;++i){
             if(str2[i]=='*'&&(str2[i+1]=='*'||i==1)){
                 printf("NO\n");
                 flag=1;
                 break;
             }
         }
        if(flag==1)
            return 0;
         for(int i=0;i<=len1;++i){
             for(int j=0;j<=len2;++j){
                  if(i==0&&j==0)
                  {
                      dp[i][j]=1;
                      continue;
                  }
                  if(i>0&&j==0)
                  {
                      dp[i][j]=0;
                      continue;
                  }
                  if(str2[j]!='*'){
                    if(i==0)
                        continue;
                    if(str1[i]==str2[j]||str2[j]=='.')
                    {
                       dp[i][j]=dp[i-1][j-1];
                    }
                   }
                   else{
                       if(i==0||str1[i]!=str2[j-1]&&str2[j-1]!='.')
                             dp[i][j]=dp[i][j-2];
                       else
                             dp[i][j]=dp[i][j-2]||dp[i-1][j-2]||dp[i-1][j];
                   }
             }
         }
         if(dp[len1][len2]==1)
             printf("YES\n");
         else{
             printf("NO\n");
         }
    }
    return 0;
}

发表于 2020-04-09 14:36:27 回复(0)

南搏万

动态规划

strs=input().strip()
exp=input().strip()
n,m=len(strs),len(exp)
dp=[[False]*(m+1) for _ in range(n+1)]
dp[0][0]=True
for i in range(1,m):
    if exp[i]=='.':
        dp[0][i+1]=dp[0][i]
    elif exp[i]=='*':
        dp[0][i+1]=dp[0][i-1]
    else:
        dp[0][i+1]=False
for i in range(n):
    dp[i+1][0]=False
    for j in range(m):
        if strs[i]==exp[j]&nbs***bsp;exp[j]=='.':
            dp[i+1][j+1]=dp[i][j]
        elif exp[j]=='*':
            if exp[j-1]=='.'&nbs***bsp;exp[j-1]==strs[i]:
                dp[i+1][j+1]=dp[i][j+1]&nbs***bsp;dp[i-1][j-1]
            else:
                dp[i+1][j+1]=dp[i+1][j-1]
if dp[n][m]:
    print('YES')
else:
    print('NO')

发表于 2020-04-01 14:49:24 回复(0)

C/C++

只会爆破

#include <iostream>
#include <cstring>

using namespace std;

int main(){
	string str,exp;
	cin>>str;
	cin>>exp;
	int flag = 0;
	
	for(int i=0;i<str.size();i++){   //如果str中有'.' 和 '*' 
		if(str[i]=='.' || str[i]=='*'){
			flag = 1;
			break;
		}
	}
	
	if(exp[0]=='*'){   // 如果exp的首字母为'*' 
		flag = 1;
	}
	
	int num=0;
	for(int i=0;i<exp.size();i++){  // 如果exp有两个连续的'*' 
		if(exp[i]=='*' && num == 1){
			flag = 1;
			break;
		}
		else if(exp[i] == '*' && num == 0){
			num = 1;
		}
		else{
			num = 0;
		}
	}
	
	int j=0;
	if(flag==1){    // 如果flag为1 
		cout<<"NO";
	}
	else{
		for(int i=0;i<str.size();i++){
			if(j<=exp.size()-1){   // 判断exp是否已经匹配完 
				if((exp[j] == '*' && exp[j-1] == str[i])  || (exp[j] == '*' && exp[j-1] == '.')){   
					if((exp[j] == '*' && exp[j-1] == str[i] && exp[j+1] == str[i]) || exp[j] == '*' && exp[j-1] == str[i] && exp[j+1] =='.')
						j++;
					continue;
				}
				else if(exp[j] == '*' && exp[j-1] != str[i]){
					j++;
					if(j<=exp.size()-1){
						if(exp[j] == str[i] || exp[j] == '.')
							j++;
						else{
							cout<<"NO";
							flag = 1;
							break;
						}	
					}
					else{
						cout<<"NO";
						flag = 1;
						break;
					}
				}
				else if(str[i] == exp[j] || exp[j] == '.'){
					j++;
				}
				else{
					cout<<"NO";
					flag = 1;
					break;
				}
			}
		}
		if(flag != 1)
			cout<<"YES";
	}
	
	
	return 0;
}

编辑于 2020-02-24 15:32:09 回复(0)

xgggggh

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();
        String exp = scanner.next();
        System.out.println(solution(s, exp));
    }

    private static String solution(String s, String exp) {
        if (!checkValid(exp)) return "NO";
        int i = 0, j = 0;
        while (i < s.length() && j < exp.length()) {
            if (exp.charAt(j) == '.') {
                i++;
                j++;
            } else if (exp.charAt(j) == '*') {
                //匹配前一个
                if (j - 1 >= 0) {
                    //可以匹配
                    if (exp.charAt(j - 1) == s.charAt(i) || exp.charAt(j - 1) == '.') {
                        while (i < s.length() && (exp.charAt(j - 1) == s.charAt(i) || exp.charAt(j - 1) == '.')) {
                            i++;
                        }
                        //匹配完了
                        if (i == s.length()) return "YES";
                        else {
                            //未匹配完,正则向前移动
                            j++;
                        }
                    } else { //匹配不了，只能匹配0次,正则向前移动
                        j++;
                    }

                }
            } else { //直接比较字母
                if (s.charAt(i) != exp.charAt(j)) return "NO";
                i++;
                j++;
            }
        }
        if (i == s.length() && j == exp.length()) return "YES";
        return "NO";
    }

    public static boolean checkValid(String exp) {
        if (exp==null||exp.length()==0) return false;
        if (exp.charAt(0) == '*') return false;
        for (int i = 0; i < exp.length(); i++) {
            if (i + 1 < exp.length() && exp.charAt(i) == '*'&& exp.charAt(i+1)=='*') {
                return false;
            }
        }
        return true;
    }
}

发表于 2019-12-11 22:29:03 回复(0)

提交观点

问题信息

字符串

上传者：小小

难度：

10条回答 37收藏 6395浏览

通过挑战的用户

查看代码

DBCGary

2022-09-04 21:17:13
DDDVE

2022-08-25 09:24:21
牛客59856...

2022-08-20 17:12:45
Keen06

2022-07-28 11:17:29
汤恒行

2022-07-26 22:36:42

字符串匹配问题

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题