当前位置:网站首页>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);
}
边栏推荐
- Teamtalk source code analysis win client
- Fabric.js 橡皮擦的用法(包含恢复功能)
- 途家木鸟美团夏日折扣对垒,门槛低就一定香吗?
- [development environment] 010 editor tool (tool download | binary file analysis template template installation | shortcut key viewing and setting)
- Quarkus学习四 - 项目开发到部署
- What is erdma? Popular science cartoon illustration
- Fabric.js 上划线、中划线(删除线)、下划线
- Golang quickly generates model and queryset of database tables
- Chinese science and technology from the Winter Olympics (III): the awakening and evolution of digital people
- MQ教程 | Exchange(交换机)
猜你喜欢

Getting started with QT - making a simple calculator

QT new project_ MyNotepad++

Yolov3 & yolov5 output result description

There is no solution to the decryption error of the remote user 'sa' and the service master password mapped from the remote server 'to the local user' (null) /sa '

Pycharm连接远程服务器

联合搜索:搜索中的所有需求

Daily learning 3

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

< 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

<口算练习机 方案开发原理图>口算练习机/口算宝/儿童数学宝/儿童计算器 LCD液晶显示驱动IC-VK1621B,提供技术支持
随机推荐
Borui data integrated intelligent observable platform was selected into the "Yunyuan production catalogue" of China Academy of communications in 2022
Development and design of animation surrounding mall sales website based on php+mysql
故事点 vs. 人天
MySQL45讲——学习极客时间MySQL实战45讲笔记—— 05 | 深入浅出索引(下)
Methods of software testing
<口算练习机 方案开发原理图>口算练习机/口算宝/儿童数学宝/儿童计算器 LCD液晶显示驱动IC-VK1621B,提供技术支持
Story point vs. Human Sky
线性dp求解 最长子序列 —— 小题三则
Route (II)
NLA natural language analysis makes data analysis more intelligent
Getting started with QT - making a simple calculator
Daily learning 2
[development environment] Dell computer system reinstallation (download Dell OS recovery tool | use Dell OS recovery tool to make USB flash disk system | install system)
由粒子加速器产生的反中子形成的白洞
Characteristics of selenium
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
Openharmony notes --------- (4)
P1908 逆序对
千元投影小明Q1 Pro和极米NEW Play谁更好?和哈趣K1比哪款配置更高?
uni-app中使用computed解决了tab切换中data()值显示的异常