当前位置:网站首页>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);
}
边栏推荐
- Fabric.js 橡皮擦的用法(包含恢复功能)
- Launcher启动过程
- [to be continued] [UE4 notes] l5ue4 model import
- Convolutional neural network (Introduction)
- Understanding of mongodb
- Development and design of animation surrounding mall sales website based on php+mysql
- [deep learning] simple implementation of neural network forward propagation
- Route (II)
- P1908 逆序对
- 跨服务器数据访问的创建链接服务器方法
猜你喜欢
每日学习2
自定义事件,全局事件总线,消息订阅与发布,$nextTick
《可供方案开发》口算训练机/数学宝/儿童口算宝/智能数学宝 LCD液晶显示驱动IC-VK1622(LQFP64封装),原厂技术支持
Pychart connects to the remote server
< schematic diagram of oral arithmetic exercise machine program development> oral arithmetic exercise machine / oral arithmetic treasure / children's math treasure / children's calculator LCD LCD driv
Packet capturing tool Fiddler learning
QT new project_ MyNotepad++
Default slot, named slot, scope slot
当贝投影4K激光投影X3 Pro获得一致好评:万元投影仪首选
selenium 元素定位方法
随机推荐
C crystal report printing
Teamtalk source code analysis win client
Design and implementation of car query system based on php+mysql
c# 水晶报表打印
go操作redis
Fabric.js 动态设置字号大小
Chapter 9: xshell free version installation
How to set QT manual layout
Using computed in uni app solves the abnormal display of data () value in tab switching
selenium 元素定位方法
《可供方案开发》口算训练机/数学宝/儿童口算宝/智能数学宝 LCD液晶显示驱动IC-VK1622(LQFP64封装),原厂技术支持
NLA自然语言分析实现数据分析零门槛
途家木鸟美团夏日折扣对垒,门槛低就一定香吗?
2022 home projector preferred! Dangbei F5 brings the ultimate audio-visual experience with its powerful audio-visual effect
万物生长大会在杭召开,当贝入选2022中国未来独角兽TOP100榜单
Tencent cloud tstor unified storage passed the evaluation of the first batch of basic file storage capabilities of the ICT Institute
Mysql5.7 installation super easy tutorial
Fabric.js 自由绘制圆形
每日学习3
腾讯云 TStor 统一存储通过信通院首批文件存储基础能力评测