当前位置:网站首页>String matching problem
String matching problem
2022-07-02 14:28:00 【N. LAWLIET】
problem :
Give an input string s( Not included . and *) And an expression p( Can contain . and *). Represents any single character , Cannot represent empty ,* Indicates any one or more preceding child characters , But it can't be used alone . Judge s and p Can it be equal ?
Example :
s=“aa”,p=“a*”
return true;
thought :
Discussion by situation , When i+1 Location is not “” when , return true To meet the j<s.length(),s[j]p[i]||p[i]‘.’, And their next position also meets the conditions ,
The second situation is i+1 The position is equal to “”. such p Jump two positions each time .
Code :
public static boolean Match(String str,String exp) {
if(str.length()==0||exp.length()==0) {
return false;
}
char[] s = str.toCharArray();
char[] e = exp.toCharArray();
return isVaild(s,e)&&process(s,e,0,0);
}
public static boolean isVaild(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 process(char[] s,char[] e,int sl,int el ) {
if(sl == s.length) {
return el == e.length;
}
//e[i] Have a character ,e[i+1]!="*"
if(el+1!=e.length&&e[el+1]!='*') {
return sl!=s.length&&(s[sl]==e[el]||e[el]=='.')&&process(s, e, sl+1, el+1);
}
//e[i] Have a character ,e[i+1]=="*"
while(sl<s.length&&(s[sl]==e[el]||e[el]=='.')) {
if(process(s, e, sl, el+2)) {
return true;
}
sl++;
}
return process(s, e, sl, el+2);
}
边栏推荐
- php链表创建和遍历
- Fabric.js 动态设置字号大小
- Daily learning 2
- Launcher startup process
- Design and implementation of car query system based on php+mysql
- QT new project_ MyNotepad++
- 联合搜索:搜索中的所有需求
- The use of TestNG, the testing framework (II): the use of TestNG XML
- Teamtalk source code analysis win client
- [development environment] Dell computer system reinstallation (download Dell OS recovery tool | use Dell OS recovery tool to make USB flash disk system | install system)
猜你喜欢

Pychart connects to the remote server

BeanUtils -- shallow copy -- example / principle

Codeforces Round #803 (Div. 2)(A~D)

In 2021, the global styrene butadiene styrene (SBS) revenue was about $3722.7 million, and it is expected to reach $5679.6 million in 2028

Daily learning 3

测试框架TestNG的使用(二):testNG xml的使用

Qt新建项目

SystemServer进程
![[development environment] 010 editor tool (tool download | binary file analysis template template installation | shortcut key viewing and setting)](/img/de/7d70f513577e93f1bde1969935a29e.jpg)
[development environment] 010 editor tool (tool download | binary file analysis template template installation | shortcut key viewing and setting)

途家木鸟美团夏日折扣对垒,门槛低就一定香吗?
随机推荐
MySQL 45 lecture - learning from the actual battle of geek time MySQL 45 Lecture Notes - 04 | easy to understand index (Part 1)
uniapp自动化测试学习
YOLOv3&YOLOv5输出结果说明
How to set QT manual layout
Golang 快速生成数据库表的 model 和 queryset
C语言高级用法--函数指针:回调函数;转换表
Dangbei projection 4K laser projection X3 Pro received unanimous praise: 10000 yuan projector preferred
Available solution development oral arithmetic training machine / math treasure / children's oral arithmetic treasure / intelligent math treasure LCD LCD driver ic-vk1622 (lqfp64 package), original te
The most complete analysis of Flink frame window function
删除元素(带过渡动画)
Default slot, named slot, scope slot
测试框架TestNG的使用(二):testNG xml的使用
HMS core machine learning service helps zaful users to shop conveniently
The global special paper revenue in 2021 was about $27 million, and it is expected to reach $35 million in 2028. From 2022 to 2028, the CAGR was 3.8%
2022家用投影仪首选!当贝F5强悍音画效果带来极致视听体验
Borui data integrated intelligent observable platform was selected into the "Yunyuan production catalogue" of China Academy of communications in 2022
Design of non main lamp: how to make intelligent lighting more "intelligent"?
The conference on the growth of all things was held in Hangzhou, and dangbei was selected into the top 100 list of future unicorns in China in 2022
c# 水晶报表打印
MQ教程 | Exchange(交换机)