首页 > 试题广场 >

字符串通配符

[编程题]字符串通配符

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

$\hspace{15pt}$ 在计算机中，通配符是一种特殊语法，广泛应用于文件搜索、数据库、正则表达式等领域。让我们来学习通配符的匹配规则：
$\hspace{23pt}\bullet\,$ $\texttt{`*'}$ 符号代表匹配 $0$ 个或以上的数字或字母；
$\hspace{23pt}\bullet\,$ $\texttt{`?'}$ 符号代表匹配 $1$ 个数字或字母；
$\hspace{23pt}\bullet\,$ 小写字母字符代表匹配自身和自身的大写字母形态；
$\hspace{23pt}\bullet\,$ 大写字母字符代表匹配自身和自身的小写字母形态；
$\hspace{23pt}\bullet\,$ 其他字符代表匹配自身。

$\hspace{15pt}$ 现在，对于给定的通配符字符串 $s$ 和目标字符串 $p$ ，不考虑大小写，请判断 $s$ 是否可以匹配得到 $p$ 。如果可以，输出 $\rm true$ ；否则，输出 $\rm false$ 。

$\hspace{15pt}$ 在本题中，给定的字符串由 ASCII 码在 $33$ 到 $126$ 范围内的可见字符构成。您可以参阅下表获得其详细信息（您可能关注的内容是，这其中不包含空格、换行）。 ../图片/AllAscii.png

输入描述:

第一行输入一个长度为 、由可见字符构成的通配符字符串 。
第二行输入一个长度为  、由可见字符构成的目标字符串 。

输出描述:

如果可以匹配得到，输出 ；否则，输出 。

示例1

输入

z
zz

输出

false

示例2

输入

Z*
zz

输出

true

说明

在这个样例中， 匹配 。注意，由于不区分大小写， 可以匹配 。

示例3

输入

?*
zz

输出

true

说明

在这个样例中， 匹配 、 匹配 。

示例4

输入

**Z
0QZz

输出

true

说明

在这个样例中，其中一种匹配方法是：
第一个  匹配 ；
第二个  匹配 ；
第三个  匹配 。

示例5

输入

??**
zz

输出

true

说明

 可以匹配  个字符。

示例6

输入

HH?*
HH##1

输出

false

说明

可被  和  匹配的字符不包含 。

算法知识视频讲解

Java

三郎君

import java.io.*; 
import java.util.*;

public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
      String value;
      while ((value = bf.readLine()) != null) {
          String target = bf.readLine();
          value = value.toLowerCase(Locale.ROOT);
          target = target.toLowerCase(Locale.ROOT);
          String regx = value.replaceAll("\\*{2,}","\\*");
          regx = regx.replaceAll("\\?","[0-9a-z]{1}");
          regx = regx.replaceAll("\\*","[0-9a-z]{0,}");
          System.out.println(target.matches(regx));
    }
}
}

发表于 2022-05-30 13:58:57 回复(0)

Python3

牛客601533329号

import re
while True:
    try:
        string1 = input().lower()
        string2 = input().lower()
        string1 = string1.replace('?', '[a-z0-9]').replace('.', '\.').replace('*', '[0-9a-z]*')
        stringRegex = re.compile(string1)
        if stringRegex.search(string2) and string2 == stringRegex.search(string2).group():
            print('true')
        else:
            print('false')
    except:
        break

发表于 2022-02-01 22:23:06 回复(1)

C++

Alvin_GLD

#include <iostream>
using namespace std;

// 一方面将字符全改为小写，另一方面检查字符合法性
bool big2small(string& s)
{
    for(char& ch : s)
    {
        if(ch >= 'A' && ch <= 'Z') ch = ch - ('A' - 'a');
        else if(ch >= 'a' && ch <= 'z') continue;
        else if(ch >= '0' && ch <= '9') continue;
        else if(ch == '*' || ch == '?' || ch == '.') continue;
        else
        {
            return false;
        }
    }
    return true;
}

bool dfs(string& s1, string& s2, int i, int j)
{
    if(i == s1.size() && j == s2.size()) return true;
    else if(i == s1.size() || j == s2.size()) return false;
    if(s1[i] == s2[j] || s1[i] == '?')
        return dfs(s1, s2, i + 1, j + 1);
    else if(s1[i] != '*') return false;
    else
    {
        // *最少能代替0个字符，最多能代替sz-j个字符
        for(int t = 0; t <= s2.size() - j; t++)
        {
            // 其中有一个情况能成功，则返回true
            if(dfs(s1, s2, i + 1, j + t)) return true;
        }
        return false;
    }
}


int main()
{
    string s1, s2;
    while(cin >> s1 >> s2)
    {
        // 检查在出现*号之前以及所有*出现完毕之后，有无不匹配字符，也就相当于无*情况
        bool finish = false;
        // 改小写，检查合法性
        if(!(big2small(s1) && big2small(s2)))
        {
            finish = true;
            cout << "false" << endl;
        }
        // 剪枝，先把*不参与部分比对好
        if(!finish)
        {
            for (int i = 0; s1[i] != '*' && i < s1.size(); i++)
            {
                if (s1[i] == s2[i] || s1[i] == '?') continue;
                else
                {
                    finish = true;
                    cout << "false" << endl;
                    break;
                }
            }
        }
        if(!finish)
        {
            int i = s1.size() - 1, j = s2.size() - 1;
            while(s1[i] != '*' && i >= 0)
            {
                if(s1[i] == s2[j] || s1[i] == '?')
                {
                    i--;
                    j--;
                }
                else
                {
                    finish = true;
                    cout << "false" << endl;
                    break;
                }
            }
        }
        if(!finish)
        {
            // 这里应该只对比*参与的中间部分就够了，懒得写了
            if(dfs(s1, s2, 0, 0)) cout << "true" << endl;
            else cout << "false" << endl;
        }
    }
    return 0;
}

发表于 2021-08-18 17:11:08 回复(1)

不想孤独终老啊

又是动态规划

发表于 2021-08-17 16:27:42 回复(0)

Java

求offer求

JAVA

递归改写为非递归

import java.util.*;
public class Main{
    public static void main(String []args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String key = in.next();
            String str = in.next();
            int num = 0;
            boolean flag = true;
            for(int i = 0; i < str.length(); i++){
                if(key.charAt(num) != '?' && key.charAt(num) != '*' &&key.charAt(num) != str.charAt(i)){
                    flag = false;
                    break;
                }
                if(key.charAt(num) == str.charAt(i) || key.charAt(num) == '?'){
                    num++;
                    continue;
                }
                if(num + 1 < str.length() && i + 1 < str.length()){
                     if(key.charAt(num + 1) == str.charAt(i + 1)){
                         num++;
                         continue;
                     }
                }
                if(key.charAt(num) == '*')
                    continue;
            }
            System.out.println(flag);
        }
        in.close();
    }
}

编辑于 2021-03-15 11:41:37 回复(2)

tigg_ZZ

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()){
            String wildcard = scanner.next();
            String target = scanner.next();
            System.out.println(matchStr(wildcard, target));
        }
    }
    public static boolean matchStr(String wildcard, String target){
        int targetIndex = 0;
        boolean startFound = false;
        for (int i = 0; i < wildcard.length(); i++){
            if (startFound){
                if ((target.charAt(targetIndex) >= '0' && target.charAt(targetIndex) <= '9') || (target.charAt(targetIndex) >= 'a' && target.charAt(targetIndex) <= 'z') || (target.charAt(targetIndex) >= 'A' && target.charAt(targetIndex) <= 'Z')){
                }else{
                    if (wildcard.charAt(i) != target.charAt(targetIndex)){
                        return false;
                    }
                    startFound = false;
                }
            }
            if (wildcard.charAt(i) == '?'){
            }else if (wildcard.charAt(i) == '*'){
                startFound = true;
            }else{
                if (wildcard.charAt(i) != target.charAt(targetIndex)){
                    return false;
                }
            }
            targetIndex += 1;
        }
        return true;
    }
}

发表于 2021-02-04 22:15:02 回复(0)

SunriseKY

def match(s1, s2):
    # 创建 dp 数组
    dp = [[0]*(len(s1) + 1) for _ in range(len(s2) + 1)]
    # 初始化 dp 数组
    for i in range(len(s2) + 1):
        if i == 0:
            dp[i][0] = 1
        else:
            dp[i][0] = 1 if dp[i - 1][0] and s2[i - 1] == '*' else 0
    # 状态转移求解 dp 数组
    for i in range(1, len(s2) + 1):
        for j in range(1, len(s1) + 1):
            if s2[i - 1] == '*':
                dp[i][j] = dp[i - 1][j] or dp[i][j - 1]
            else:
                dp[i][j] = 1 if dp[i - 1][j - 1] and (s2[i - 1] == '?'&nbs***bsp;s2[i - 1] == s1[j - 1]) else 0
    # 返还匹配结果
    return dp[-1][-1]

while True:
    try:
        s2 = input()
        s1 = input()
        print('true' if match(s1, s2) else 'false')
    except:
        break

编辑于 2020-09-15 16:34:24 回复(1)

Python

ShadowAnt_TC

def error_index(string):
    # 输出非法字符的位置
    ans = []
    for i in range(len(string)):
        c = string[i]
        if c.isalpha() or c.isnumeric() or c=='*' or c=='?':
            continue
        else:
            ans.append(i)
    return ans

def split_by_index(string, index):
    # 通过非法符号的位置进行划分
    ans = []
    index.insert(0, -1)
    index.append(len(string))
    lengh = len(index)
    for i in range(lengh-1):
        temp = string[index[i]+1: index[i+1]]
        if temp!='':
            ans.append(temp)
    return ans

def error_cmp(str1,str2,index1,index2):
    # 比较非法字符是否一样
    for i,j in zip(index1, index2):
        if str1[i]!=str2[i]:
            return False
    return True

def eq(str1, str2):
    # 比较通配符 str2是纯字母数字
    len1, len2 = len(str1), len(str2)
    if len1!=len2 and '*' not in str1:
        return False
    matrix = [[False for j in range(len2)] for i in range(len1)]
    if str1[0]=='*' or str1[0]=='?': matrix[0][0] = True
    else: 
        if str1[0]==str2[0]: matrix[0][0] = True

    for i in range(1, len1):
        if str1[i]=='*' and matrix[i-1][0]:
            matrix[i][0] = True
        else:
            matrix[i][0] = False
    
    # 重点重点重点重点重点重点重点重点重点重点重点重点重点重点重点重点重点
    for i in range(1, len1):
        for j in range(1, len2):
            if str1[i]=='*':
                matrix[i][j] = matrix[i-1][j] or matrix[i][j-1]
            else:
                matrix[i][j] = matrix[i-1][j-1] and (str1[i]=='?'&nbs***bsp;str1[i]==str2[j])
    return matrix[len1-1][len2-1]
            

while True:
    try:
        error = 0
        expression, todo = input(), input()
        exp_index, todo_index = error_index(expression), error_index(todo)
        if len(exp_index)!= len(todo_index) or not error_cmp(expression, todo, exp_index, todo_index):
            error = 1
            break
        exp_split, todo_split = split_by_index(expression, exp_index), split_by_index(todo, todo_index)
        for str1,str2 in zip(exp_split, todo_split):
            if not eq(str1, str2):
                error = 1
                break
        if error: 
            print('false')
        else: 
            print('true')
    except:
        break

思想是先找字符以外的字符，再对这些非法字符进行split，比较这些非法字符是否一样，不一样直接退出。

再对分割后的子串进行通配符比较。

https://blog.csdn.net/weixin_38823568/article/details/81482046

https://blog.csdn.net/gldemo/article/details/47678159

编辑于 2020-07-30 22:02:50 回复(0)

Python

君临天下201804050931706

while True:
    try:
        str1 = input()
        str2 = input()
        x = 0
        y = 0
        flag=True
        while x<len(str1)-1 and y<len(str2)-1:
            if(str1[x]==str2[y] or str1[x]=="?"):
                x+=1
                y+=1
            elif(str1[x]=="*"):
                if(str1[x+1]==str2[y+1]):
                    x+=1
                    y+=1
                else:
                    y+=1
            else:
                flag=False
                break
        if(flag):
            print("true")
        else:
            print("false")
    except:
        break

发表于 2020-07-13 09:24:38 回复(1)

freshone

#include <iostream>
(720)#include <string>
using namespace std;

int main() {
        string str1;
        string str2;
        while (cin >> str1 >> str2) {
                int res = 1;
                int i = 0;
                int flag = 0;
                for (auto c : str2) {
                        if (flag && c == str1[i]) {
                                flag = 0;
                        }
                        if (str1[i] == '*') {
                                flag = 1;
                        }
                        if (c != str1[i] && str1[i] != '?' && !flag) {
                                res = 0;
                        }
                        i++;
                }
                if (res)
                        cout << "true" << endl;
                else
                        cout << "false" << endl;
                
        }
}

发表于 2020-03-10 22:23:26 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

int main()
{     string s1,s2;     while(cin>>s1>>s2)      {         int l1=s1.length(),l2=s2.length();         vector<vector<int>> dp(l1+1, vector<int>(l2+1,0));         dp[0][0] = 1;         for(int i=1;i<=l1;i++)         {             char c1 = s1[i-1];             dp[i][0] = dp[i-1][0] && (c1=='*');             for(int j=1;j<=l2;j++)             {                 char c2 = s2[j-1];                 if(c1=='*')                     dp[i][j] = dp[i-1][j] || dp[i][j-1];                 else                     dp[i][j] = dp[i-1][j-1] && (c1=='?' || c1==c2);             }         }         cout<<((dp[l1][l2]==true)?"true":"false")<<endl;     }     return 0;
}

发表于 2019-01-02 23:55:09 回复(1)

C/C++

201802270939813

//不用正则表达式的算法:但是a*bc匹配abc失败
#include <string>
#include <iostream>
using namespace std;
bool isMatched(string s1,string s2);
int main()
{
    string s1,s2;
    while(cin>>s1>>s2)
    {
        if(isMatched(s1,s2))    cout<<"true"<<endl;
        else    cout<<"false"<<endl;
    }
}
bool isMatched(string s1,string s2)//s1模式串，s2目标串
{
    unsigned i=0,j=0;//i是s1的指针，j是s2的指针
    for(;i<s1.size()&&j<s2.size();)
    {
        if(s1[i]=='?')//当前位置匹配
        {
            i++;j++;
        }
        else if(s1[i]=='*')
        {
            if(i==s1.size()-1)  return true;//如果当前i是s1最后一个，肯定是匹配的；
            if(s1[i+1]!='?')//如果i+1位置不是？，比如3*e匹配3wece,那么在s2中找到第一个不等于s1[i+1]即'e'的位置j
                while(s2[j+1]!=s1[i+1]&&j+1<s2.size())
                    j++;
            else//如果i+1位置是？，比如3*?e匹配3wece,那么在s2中找到第一个不等于s1[i+2]即'e'的位置j
                while(s2[j+1]!=s1[i+2]&&j+1<s2.size())
                    j++;
            //如果i不是s1的最后一个位置但是s2已经读到最后了，则匹配不成功
            if(i<s1.size()-1&&j==s2.size()-1)   return false;
            //下面两行：如果i+1位置是？，i应前进两位，否则前进一位
            if(s1[i+1]=='?')    i++;
            i++;j++;
        }
        else
        {
            if(s1[i]!=s2[j])    return false;
            i++;j++;
        }
    }
    return true;//s1扫描结束都没有退出，则匹配成功
}

编辑于 2018-05-30 21:53:52 回复(0)

Java

billSeGates

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			String ptn = sc.nextLine();
			String str = sc.nextLine();
			StringBuffer sb = new StringBuffer();
			for (int i = 0; i < ptn.length(); i++) {
				if (ptn.charAt(i) == '?') {
					sb.append(".{1}");
				} else if (ptn.charAt(i) == '*') {
					sb.append(".{0,}");
				} else {
					sb.append(ptn.charAt(i));
				}
			}
			System.out.println(str.matches(sb.toString()));
		}
	}

}

ps: 用正则表达式做的，有种胜之不武的感觉。

发表于 2017-08-16 01:01:25 回复(2)

Java

IM_Rocket

虽然通过了，但是我这个程序有点不足，无法正确的判断a* 与 a是否匹配
import java.util.Scanner;

public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		while (scan.hasNext()) {
			String pattern = scan.nextLine();
			String target = scan.nextLine();
			System.out.println(match(pattern, target, 0, 0));
		}

	}

	public static boolean match(String pattern, String target, int index1,
			int index2) {
		if (index1 == pattern.length()  && index2 == target.length() ) {
			return true;
		}
		if (index1 >= pattern.length() || index2 >= target.length()) {
			return false;
		}
		if (pattern.charAt(index1) == '?') {
			return match(pattern, target, index1 + 1, index2 + 1);
		} else if (pattern.charAt(index1) == '*') {
			// 匹配0个一个或者多个
			return match(pattern, target, index1 + 1, index2)
					|| match(pattern, target, index1 + 1, index2 + 1)
					|| match(pattern, target, index1, index2 + 1);
		} else if (pattern.charAt(index1) == target.charAt(index2)) {
			return match(pattern, target, index1 + 1, index2 + 1);
		}
		return false;
	}

}

发表于 2017-04-30 08:44:27 回复(2)

C/C++

牛客2887214号

#include<iostream>
#include<string>
#include<vector>
using namespace std;
//给一个两个都可以含有通配符的比较方法string s,p;
/*
1.s[i] == p[j],且均不等于* dp[i][j] = dp[i-1][j-1];
2.s[i] != p[j] 且均不等于* 或者？，dp[i][j] = 0; 3.s[i] != p[j],两者其一为普通字符，另外一个为？，dp[i][j] = dp[i-1][j-1]; 4.s[i] != p[j],p[j] ==*,dp[i][j] = (dp[i][j-1]||dp[i-1][j-1]||dp[i-2][j-1]||...||dp[1][j-1]);
5.s[i] != p[j],s[i] == * ,dp[i][j] = (dp[i-1][j]||dp[i-1][j-1]||dp[i-1][j-2]||...||dp[i-1][1]); 6.s[i] == p[j] == *,dp[i][j] = (dp[i][j-1]||dp[i-1][j-1]||...dp[1][j-1] ||dp[i-1][j]||dp[i-1][j-1]||dp[i-1][j-2]||...||dp[i-1][1]); */
class Solution {
public:
	bool isMatch(string str1,string str2) {
		int len1 = str1.length();
		int len2 = str2.length();
		if (str1 == ""){//特殊情况
			if (str2 == "") return true;
			else {
				int j = 0;
				while (j != len2){
					if (str2[j] != '*')
						return false;
					++j;
				}
				return true;
			}
		}
		if (str2 == ""){//特殊情况
			if (str1 == "") return true;
			else {
				int i = 0;
				while (i != len1){
					if (str1[i] != '*')
						return false;
					++i;
				}
				return true;
			}
		}
		vector<vector<bool> > dp(len1 + 1, vector<bool>(len2 + 1, false));
		dp[0][0] = true;
		for (int i = 1; i <= len1; ++i){//方便起见，i、j均指第i、j个字符,需要注意的是取字符串中字符时候的下标
			for (int j = 1; j <= len2; ++j){
				if (str1[i - 1] == str2[j - 1]){//处理相等的情况，这又包含了两种情况
					if (str1[i - 1] != '*'){//情况1,两个普通字符相等
						dp[i][j] = dp[i - 1][j - 1];
					}
					else{//情况2,两个字符均为'*';
						for (int index = i; index >= 0; --index){
							dp[i][j] = dp[index][j - 1];
							if (dp[i][j]) break;
						}
						for (int index = j; index >= 0; --index){
							dp[i][j] = dp[i - 1][index];
							if (dp[i][j]) break;
						}
					}
				}// end ==
				else{//处理不相等的情况，这又包含了四种情况
					if (str1[i - 1] != '?' && str1[i - 1] != '*'){//str1[i-1]是普通字符
						if (str2[j - 1] != '?' && str2[j - 1] != '*'){//str2[j-1]也是普通字符
							dp[i][j] = 0;
						}
						else if (str2[j - 1] == '?')//str2[j-1] == '?';
							dp[i][j] = dp[i - 1][j - 1];
						else {//str2[j-1] == '*';
							for (int index = i; index >= 0; --index){
								dp[i][j] = dp[index][j - 1];
								if (dp[i][j]) break;
							}
						}
					}
					else if (str1[i - 1] == '?'){//str1[i-1] == '?'
						if (str2[j - 1] != '*'){//str2[j-1]是普通字符
							dp[i][j] = dp[i - 1][j - 1];
						}
						else {//str2[j-1] == '*'
							dp[i][j] = dp[i - 1][j - 2];
							if (!dp[i][j]){
								for (int index = i; index >= 0; --index){
									dp[i][j] = dp[index][j - 1];
									if (dp[i][j]) break;
								}
							}
						}
					}
					else {//str1[i-1] == '*'
						if (str2[j - 1] == '?'){//比普通的字符多一次匹配的机会
							dp[i][j] = dp[i - 2][j - 1];
						}
						if (!dp[i][j]){
							for (int index = j; index >= 0; --index){
								dp[i][j] = dp[i - 1][index];
								if (dp[i][j]) break;
							}
						}
					}
				}
			}//end j
		}//end i
		return dp[len1][len2];
	}
};
int main() {
	string str1, str2;
	Solution s;
	while (cin >> str1 >> str2)
		if (s.isMatch(str1, str2)) cout << "true" << endl;
		else cout << "false" << endl;
}

编辑于 2017-03-18 18:25:22 回复(0)

超小白

正确的方法，动态规划，类似LCS问题。

#include<iostream>
#include<string>    
#include<cstring>
using namespace std;
bool match_string(string str, string strpattern)
{
	int nStr = str.size();
	int nPatt = strpattern.size();
	int** dp = new int*[nStr + 1];
	for (int k = 0; k <= nStr; k++) {
		dp[k] = new int[nPatt + 1];
		memset(dp[k], 0, (nPatt + 1)*sizeof(int));
	}

	int t = 0;
	while(strpattern[t] == '*')
	{
		for (int i = 0; i <= nPatt; ++i)
		{
			dp[t][i] = 1;
		}
		for (int j = 0; j < nStr; ++j){
			dp[j][t] = 1;
		}
		++t;
	}
	dp[0][0] = 1;

	for (int j = 1; j <= nPatt; ++j)
	{
		for (int i = 1; i <= nStr; ++i)
		{
			if ((strpattern[j - 1] == '?' && str[i - 1] != '\0') || strpattern[j - 1] == str[i - 1]){
				dp[i][j] = dp[i - 1][j - 1];
			}
			else if (strpattern[j - 1] == '*'){
				if (dp[i][j - 1] == 1 || dp[i - 1][j] == 1 || dp[i - 1][j - 1] == 1)
					dp[i][j] = 1;
			}
		}
	}

	bool ret = (dp[nStr][nPatt] == 1 ? true : false);
	for (int k = 0; k <= nStr; k++)
		delete[] dp[k];
	delete dp;
	return ret;
}
int main(int argc, char** argv)
{
	string s1, s2;
	while (cin >> s1 >> s2){
		if (match_string(s2, s1))
			cout << "true" << endl;
		else
			cout << "false" << endl;
	}
	return 0;
}

发表于 2016-08-30 10:24:54 回复(1)

lzdcqu

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
bool solve(string str1,string str2)
{
	if(str1.length()>str2.length())
		return false;
	int i,j;
	for(i=0,j=0;i<str1.length(),j<str2.length();)
	{
		if(str1[i]=='?')
		{
			i++;
			j++;
		}
		else if(str1[i]=='*')
		{
			//i++;j++;//只用这一句也能通过
            if(i==str1.length()-1)
				return true;
			else if(i<str1.length()-1)
			{
				i++;j++;
			}
		}
		else if(str1[i]!=str2[j])
			return false;
		else
		{
			i++;j++;
		}
	}
	return true;
}
int main()
{
	string str1,str2;
	while(cin>>str1>>str2)
	{
		if(solve(str1,str2))
			cout<<"true"<<endl;
		else
			cout<<"false"<<endl;
	}
	return 0;
}

发表于 2016-08-15 11:20:35 回复(2)

wuing

#include<iostream>

#include<string>

using namespace std;

int main()

{

string a,b;

while(cin>>a>>b)

{

int bsize=b.size();

int asize=a.size();

int aindex=0,bindex=0,flag=0;

while(bindex!=bsize)

{

switch(a[aindex])

{

case('*'):

if(a[aindex+1]==b[bindex]&&a[aindex+1]==b[bindex+1])

{

aindex=aindex+2;

bindex=bindex+2;

}

else if(a[aindex+1]==b[bindex]&&a[aindex+1]!=b[bindex+1])

{

aindex=aindex+2;

bindex++;

}

else

bindex++;

break;

case('?'):

aindex++;bindex++;break;

default:

if(a[aindex]==b[bindex])

{

aindex++;

bindex++;

}

else

flag=1;

break;

}

if(flag)

break;

}

if(flag)

cout<<"false"<<endl;

else

cout<<"true"<<endl;

}

return 0;

}

发表于 2016-03-29 19:09:46 回复(1)

牛客873413号

// 用递归就可以了
#include <iostream>
#include <string>
using namespace std;

bool match(const char* pattern, const char *str)
{
	if (*pattern == '\0' && *str == '\0')
		return true;
	if (*pattern == '\0' || *str == '\0')
		return false;

	if (*pattern == '?')
	{
		return match(pattern + 1, str + 1);
	}
	else if (*pattern == '*')
	{
		// 匹配0个1个或多个
		return match(pattern + 1, str) || match(pattern + 1, str + 1) || match(pattern, str + 1); 
	}
	else if (*pattern == *str)
	{
		return match(pattern + 1, str + 1);
	}

	return false;
}
int main(void)
{
	string pattern, str;
	while (cin >> pattern >> str)
	{
		bool ret = match(pattern.c_str(), str.c_str());
		if (ret)
			cout << "true" << endl;
		else
			cout << "false" << endl;
	}
	return 0;
}

发表于 2016-09-17 20:14:12 回复(20)

C/C++

小南ko

这道题链接讲得很详细，我的也是参考它的
http://www.mamicode.com/info-detail-986984.html
******************************************************************************************
#include<string>
#include<iostream>
#include<vector>
using namespace std;
int match_string(string m_str,string w_str) //match wildcard 通配符
{
    int m_len = m_str.size();
    int w_len = w_str.size();
    vector<vector<int> > b_dp(w_len+1,vector<int>(m_len+1,0));
    //多加一行一列作为初始初值所用
    b_dp[0][0] = 1;
    for(int i=1;i <=w_len;i++)
    {
        char ch = w_str[i-1];
        ////设置每次循环的初值，即当星号不出现在首位时，匹配字符串的初值都为false
        b_dp[i][0] = b_dp[i-1][0]&&(ch=='*');
        for(int j=1;j<=m_len;j++)
    	{
            char ch2 = m_str[j-1];
        	if(ch=='*')
                b_dp[i][j]=b_dp[i-1][j]||b_dp[i][j-1]; //当匹配字符为*号时，状态取决于上面状态和左边状态的值
            else
                b_dp[i][j]=b_dp[i-1][j-1]&&(ch=='?'||ch2==ch);
    	}
    }
    return b_dp[w_len][m_len];
    
    
    
}

int main()
{
    string str1,str2;
    while(cin >> str1 >> str2)
    {
       int rst =  match_string(str2,str1);
       if(rst==1)
           cout << "true" << endl;
        else
           cout << "false" << endl;
    }
    
}

发表于 2016-09-09 20:44:12 回复(6)

提交观点

问题信息

字符串

难度：

323条回答 3105收藏 37544浏览

通过挑战的用户

查看代码

猪儿拱

2023-02-26 22:43:42
帅阿衰

2023-01-08 10:20:13
hnSS

2023-01-02 16:02:27
芊樱烛渊

2022-10-30 20:15:16
牛客39961...

2022-10-30 10:33:48

字符串通配符

输入描述:

输出描述:

输入

输出

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题