首页 > 试题广场 >

伪正则表达式

[编程题]伪正则表达式
  • 热度指数:1012 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
判断一个数字串是否匹配一个表达式,具体如下:
1)表达式m:一定不为空,只能由数字和“*”构成,其中的“*”表示匹配一个或多个“它前面所有非”*“的数字的和值除以10的余数”;“*”如果在最前面或其前面都是“*”,则只可以是任意一个数字。
2)数字串s:可能为空,只能由数字构成,不能包含其它字符。
3)是否匹配:匹配要求覆盖整个数字串s,而不是某一部分匹配。

解题要求:不能将m转写成标准正则表达式来解题,需要自己编程实现匹配算法。

注意,对应objc语言,系统里的@autoreleasepool {} 需要改写成如下形式
#import <Foundation/Foundation.h>
//strcmp
//NSString:
//- (NSArray<NSString *> *)componentsSeparatedByCharactersInSet:(NSCharacterSet *)separator
//- (unichar)characterAtIndex:(NSUInteger)index;
//- (NSString *)substringWithRange:(NSRange)range;

int main(int argc, const char * argv[]) {
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
    //...
    //add your code
    //...
    [pool drain];
    return 0;
}


输入描述:
见输入样例,其中最后一行的0表示结束输入


输出描述:
YES:匹配

NO:不匹配
示例1

输入

3
1*
11111
**1
121
**1
1221
0

输出

YES
YES
NO

说明

3表示case数有3个
case 1:1*是表达式,11111是数字串,*前面所有数字的和值除以10的余数为1,*表示匹配1个或1个以上的前面数字”1“,刚好“1111”符合匹配规则,所以,输出YES。
case 2:**1是表达式,121是数字串,第一个*在最前面,可以是任意数字,与“1”匹配;第二个“*”因为前面都是“*”,所以可以是任意一个数字,与“2”匹配。总体看,两者符合匹配规则,输出YES。
case 3:**1是表达式,1221是数字串,第一个*与“1”匹配,第二个*与“2”匹配,但只能匹配一个“2”,整体不符合匹配规则,所以,输出NO。
示例2

输入

3
1*
11111
21*
2103
22*
22*
0

输出

YES
NO
NO

说明

3表示case数有3个
case 1:1*是正则表达式,11111是数字串,两者符合匹配规则,所以,输出YES。
case 2:21*是正则表达式,2103是数字串,*前面所有数字的和值除以10的余数为3,刚好“03”并不符合匹配规则,所以,输出NO。
case 3:22*是正则表达式,22*是数字串,但是因为其中包含了*这样的非数字字符,并不符合匹配规则,所以,输出NO。
头像 牛客题解官
发表于 2020-06-05 17:36:45
题解 题目难度:中等 知识点:查找、递归 解题思路:整道题其实不难,在题目的描述过程中需要读懂题意。其实就是一道字符匹配的题,整个过程只要依次对字符串m和s进行对比就可以了。稍微不一样的地方时'*'代表的含义,所以这边在匹配中多添加了一个参数cur来描述目前的余数,因为刚好是除以10的余数,所以cu 展开全文
头像 自无不可
发表于 2020-06-16 19:03:57
官方题解的java版本,加了点细节。题目里比较容易引起歧义的应该是匹配的定义吧,需要的是完全覆盖,就是s变换以后不能比m长也不能比m短,就是刚好覆盖才算匹配。 import java.util.Scanner; public class Main { static String s1,s2; 展开全文