检查给定的字符串是否遵循给定的模式

Question

我的一个朋友刚刚在谷歌接受采访并被拒绝,因为他无法解决这个问题.

我在几天内有自己的面试,似乎无法找到解决问题的方法.

这是问题:

给你一个模式,比如[abab].你也会得到一个字符串,例如"redblueredblue".我需要编写一个程序来告诉字符串是否遵循给定的模式.

几个例子:

模式:[abba]字符串:catdogdogcat返回1

模式:[abab]字符串:redblueredblue返回1

模式:[abba]字符串:redblueredblue返回0

我想到了一些方法,比如获取模式中唯一字符的数量,然后找到字符串的许多唯一子字符串,然后使用hashmap与模式进行比较.然而,如果a的子串是b的一部分,那么结果证明是个问题.

如果你们中的任何人能够帮助我,那真的很棒.:)

更新:

添加信息:模式中可以有任意数量的字符(az).两个字符不代表相同的子字符串.此外,字符不能表示空字符串.

Answer 1

我能想到的最简单的解决方案是将给定的字符串分成四个部分并比较各个部分.你不知道过了多久a或者b是,但两者a可相同的长度,以及bs为.因此,如何划分给定字符串的方式数量不是很大.

示例:pattern = [a b a b],给定字符串= redblueredblue(总共14个字符)

1. |a|(长度a)= 1,然后as 为2个字符,s 为12个字符b,即|b|= 6.分割字符串= r edblue r edblue.哇,这匹配马上!
2. (只是出于好奇)|a| = 2, |b| = 5- >划分字符串= re dblue re dblue- >匹配

示例2:pattern = [a b a b],string = redbluebluered(总共14个字符)

1. |a| = 1, |b| = 6- >划分字符串= r edblue b luered- >不匹配
2. |a| = 2, |b| = 5- >划分字符串= re dblue bl uered- >不匹配
3. |a| = 3, |b| = 4- >划分字符串= red blue blu ered- >不匹配

其余的不需要检查,因为如果您切换a,b反之亦然,情况是相同的.

什么是[abcabc]的模式？

Answer 2

你是不是只需要使用反向引用将模式转换为正则表达式,即类似这样的东西(加载了"re"模块的Python 3):

>>> print(re.match('(.+)(.+)\\2\\1', 'catdogdogcat'))
<_sre.SRE_Match object; span=(0, 12), match='catdogdogcat'>

>>> print(re.match('(.+)(.+)\\1\\2', 'redblueredblue'))
<_sre.SRE_Match object; span=(0, 14), match='redblueredblue'>

>>> print(re.match('(.+)(.+)\\2\\1', 'redblueredblue'))
None

正则表达式看起来非常简单.如果需要支持9个以上的backref,可以使用命名组 - 请参阅Python regexp文档.