一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 905|回复: 6
收起左侧

[算法题] 求问一道substring题目(可能含有星号)

[复制链接] |试试Instant~ |关注本帖
yueliu2366 发表于 2016-6-8 05:53:09 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
实现boolean isSubstring(String s, String p). 如果p是s的substring,就返回true。 p可以是带有'*'的,一个'*'可以代表0或者多个任意字符。请问这题怎么解答比较好呢?
yingy4 发表于 2016-6-8 14:26:24 | 显示全部楼层
在地铁上随便想的,有问题的话见谅。
用*分割p,看分割出来的string是不是依次序存在在s里面,是的话就返回true,有任何一个不在s里就返回false
回复 支持 反对

使用道具 举报

yingy4 发表于 2016-6-8 14:29:19 | 显示全部楼层
yingy4 发表于 2016-6-8 14:26
在地铁上随便想的,有问题的话见谅。
用*分割p,看分割出来的string是不是依次序存在在s里面,是的话就返回 ...

还要注意保证分割出来的string在s里出现的顺序和在p里是一致的
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-8 14:59:07 | 显示全部楼层
楼上做法感觉可行,简单了写了下,没有处理开头是*或者连续出现*的情况。。

  1. bool isSubStr(string s, string p){
  2.    
  3.     string strInP;
  4.     int i =0;
  5.     for(; i<p.length(); i++){
  6.         if(p[i]=='*')
  7.             break;
  8.     }
  9.     strInP = p.substr(0, i);
  10.    
  11.     int foundIndex = s.find(strInP);
  12.     if(foundIndex==-1)
  13.         return false;
  14.    
  15.     return i>=p.length()||isSubStr(s.substr(foundIndex+strInP.length()), p.substr(i+1));
  16.    
  17. }
复制代码
回复 支持 反对

使用道具 举报

 楼主| yueliu2366 发表于 2016-6-8 20:51:17 | 显示全部楼层
yingy4 发表于 2016-6-8 14:26
在地铁上随便想的,有问题的话见谅。
用*分割p,看分割出来的string是不是依次序存在在s里面,是的话就返回 ...

感觉可行,而且是线性的时间复杂度,厉害!
回复 支持 反对

使用道具 举报

 楼主| yueliu2366 发表于 2016-6-8 20:51:46 | 显示全部楼层
handsomecool 发表于 2016-6-8 14:59
楼上做法感觉可行,简单了写了下,没有处理开头是*或者连续出现*的情况。。

好像开头是*或者连续出现*也是相同的思路啊
回复 支持 反对

使用道具 举报

handsomecool 发表于 2016-6-9 02:09:20 | 显示全部楼层
yueliu2366 发表于 2016-6-8 20:51
好像开头是*或者连续出现*也是相同的思路啊

对,我的意思是code可能有bug或者corner case没有handle, 只是写个大致思路
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 10:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表