当前位置:网站首页>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);
}
边栏推荐
- What is erdma? Popular science cartoon illustration
- 自定义事件,全局事件总线,消息订阅与发布,$nextTick
- Mysql5.7 installation super easy tutorial
- 全屋Wi-Fi:一个谁也解决不好的痛点?
- 你知道Oracle的数据文件大小有上限么?
- 一般来讲,如果频繁出现inconsistent tab and space的报错
- HMS core machine learning service helps zaful users to shop conveniently
- Systemserver process
- Essential elements of science fiction 3D scenes - City
- 故事点 vs. 人天
猜你喜欢
Use of swagger
什么是 eRDMA?丨科普漫画图解
How kaggle uses utility script
Daily learning 2
Fabric.js 缩放画布
Development and design of animation surrounding mall sales website based on php+mysql
<口算練習機 方案開發原理圖>口算練習機/口算寶/兒童數學寶/兒童計算器 LCD液晶顯示驅動IC-VK1621B,提供技術支持
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%
QT new project_ MyNotepad++
[to be continued] [UE4 notes] l5ue4 model import
随机推荐
docker mysql
Qt新建项目
< schéma de développement de la machine d'exercice oral > machine d'exercice oral / trésor d'exercice oral / trésor de mathématiques pour enfants / lecteur LCD de calculatrice pour enfants IC - vk1621
Go operation redis
Pycharm连接远程服务器
Method of creating linked server for cross server data access
NLA自然语言分析实现数据分析零门槛
数据湖(十一):Iceberg表数据组织与查询
Story point vs. Human Sky
Characteristics of selenium
Simple introduction to ENSP
PyQt5_QScrollArea内容保存成图片
Penetrate the remote connection database through the Intranet
Fabric.js 动态设置字号大小
Daily learning 3
OpenHarmony笔记-----------(四)
Selenium element positioning method
默认插槽,具名插槽,作用域插槽
Yyds dry goods inventory software encryption lock function
<口算練習機 方案開發原理圖>口算練習機/口算寶/兒童數學寶/兒童計算器 LCD液晶顯示驅動IC-VK1621B,提供技術支持