面试官了问了10分钟左右的项目,就直接开始做题了😰
题目描述:
字符串模式匹配
-
模式匹配定义：某个长度为3的子串满足：第一个字母和第三个字母一样，且和第二个字母不一样，就认为是匹配的
-
给一个任意长度的字符串，要求输出最后不满足上面模式的子串
eg: 满足要求的子串：aba，xyx，不满足要求的123，122
输入：abxyxc，输出：abc，理解: 去掉满足要求的xyx
输入：dabxyxac，输出：dc，理解: 首先找到xyx，删除之后变成dabac，继续删除，dc无法再删除
hxdm有没有好的解法? 我的解法是,找到满足的子串之后，从它的两侧扩展找符合要求的子串
即，dabxyxac 我找到 xyx 之后不删除，继续去找xyx的左右，发现left=ab，right=a，也是满足要求的，就扩展要删除的区域，直到找不到匹配为止，然后从删除区域离开找下一个 匹配的子串
——只需要一次遍历即可.
存在问题:
eg：babxyxacb，如果按照上面的找到第一个匹配，即bab，它并没有办法扩展了，为第一个删除区域，xyx是第二个删除区域，所以结果是acb
但是如果bab不删除,先删除xyx，扩展的时候发现 left=ab，right=a，也是满足要求的; 继续扩展left=b，right=cb，也是满足要求的，所以结果是""(空字符串)
不知道该用何种思路解题了
全部评论
(0) 回帖