百度Android1面算法题

面试官了问了10分钟左右的项目,就直接开始做题了😰
题目描述:

字符串模式匹配

  1. 模式匹配定义:某个长度为3的子串满足:第一个字母和第三个字母一样,且和第二个字母不一样,就认为是匹配的

  2. 给一个任意长度的字符串,要求输出最后不满足上面模式的子串

eg: 满足要求的子串:aba,xyx,不满足要求的123,122

输入:abxyxc输出:abc,理解: 去掉满足要求的xyx

输入:dabxyxac,输出:dc,理解: 首先找到xyx删除之后变成dabac继续删除dc无法再删除

hxdm有没有好的解法? 我的解法是,找到满足的子串之后,从它的两侧扩展找符合要求的子串
dabxyxac 我找到 xyx 之后不删除,继续去找xyx的左右,发现left=abright=a也是满足要求的就扩展要删除的区域,直到找不到匹配为止,然后从删除区域离开找下一个 匹配的子串
——只需要一次遍历即可.
存在问题:
eg:babxyxacb,如果按照上面的找到第一个匹配,即bab,它并没有办法扩展了,为第一个删除区域,xyx是第二个删除区域,所以结果是acb
                          但是如果bab不删除,先删除xyx,扩展的时候发现 left=ab,right=a,也是满足要求的; 继续扩展left=b,right=cb,也是满足要求的,所以结果是""(空字符串)
不知道该用何种思路解题了
#百度校招提前批内推##百度##面经#
全部评论

相关推荐

点赞 1 评论
分享
牛客网
牛客企业服务