shopee 笔试最后一题求 AC 解

通配符匹配。输入两行字符串，第一行是正则表达式，第二行是不含通配符的字符串。如果完全匹配输出 1，否则输出 0.

? 匹配一个字符

# 匹配 0 或 1 个字符

* 匹配 0 或多个字符

个人只有77%🤣🤣

import java.util.*;

public class Main {


    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        //while (true) {
            String reg = scanner.nextLine();
            String str = scanner.nextLine();
            //* ? -
          //  if(reg.equals("."))
           //     break;
            int i = 0, j = 0;
            if (match(reg, str, 0, 0))
                System.out.println(1);
            else
                System.out.println(0);
       // }
    }

    public static boolean match(String reg,String str,int i,int j){
        if(reg.length()==i && str.length()==j)
            return true;
        if(reg.length()==i && str.length()!=j)
            return true;
        if(reg.length()!=i && str.length()==j){
            for(int p=i;p<reg.length();p++){
                char c=reg.charAt(p);
                if(c!='*' && c!='#')
                    return true;
            }
            return true;
        }
        switch (reg.charAt(i)){
            case '?':
                return match(reg,str,i+1,j+1);
            case '#':
                return match(reg,str,i+1,j+1) || match(reg,str,i+1,j);
            case '*':
                while (i<reg.length() && reg.charAt(i)=='*'  )
                    i++;
                for(int p=j;p<str.length();p++){
                    if(match(reg,str,i,p))
                        return true;
                }
                return false;
           default:return reg.charAt(i)==str.charAt(j) && match(reg,str,i+1,j+1);

        }
    }
}

#Shopee##笔试题目#

全部评论

推荐最新楼层

青盏一座

南京理工大学

这一题直接输出1有70+%，我过了96%，没时间了

点赞回复分享

发布于 2019-09-14 20:59

招行信用卡中心内推之星

北京大学 C++

过了92.59%😐

点赞回复分享

发布于 2019-09-14 23:35

行走的算法

门头沟学院 C++

#include <iostream> #include <string> using namespace std; bool match(char* pat, char* res) { if (*pat == '\0'&&*res == '\0') return true; if (*pat != '\0'&&*res == '\0') { while (*pat != '\0') { if (*pat == '#' || *pat == '*') { pat++; } else return false; } return true; } if (*pat == '\0'&&*res != '\0') { return false; } if (*pat == '?') return match(pat + 1, res + 1); if (*pat == '#') { return match(pat + 1, res + 1) || match(pat + 1, res); } if (*pat== '*') { return match(pat + 1, res) || match(pat + 1, res+1)|| match(pat, res + 1); } if(*pat==*res) return match(pat + 1, res + 1); return false; } int main() { string strt, strr; getline(cin, strt); getline(cin, strr); char* pat = new char[strt.size()]; char* res = new char[strr.size()]; for (int i = 0; i < strt.size(); i++) { pat[i] = strt[i]; } for (int i = 0; i < strr.size(); i++) { res[i] = strr[i]; } bool flag = match(pat ,res); if (flag == true) cout << 1 << endl; else cout << 0 << endl; return 0; } //AC 90%+ 显示超时

点赞回复分享

发布于 2019-09-14 21:04

4123

楼主

浙江大学 Java

我好像找到问题了。。。 if(c!='*' && c!='#') return true; 应该是return false;

点赞回复分享

发布于 2019-09-14 21:02

野径入桑麻

浙江大学算法工程师

题目不一样，我是换成千分位表示和找出相同数字组成的比源数字小的最大数字

点赞回复分享