2017-03-15 277 views
0

嗨有一个字符串,如这样的:在原始字符串中查找隐藏的子字符串?

orig = "hbeojllok" 

,并想知道是否有在这串中的某个隐子。例如,我们可以在其中找到单词'hello':h b e oj llo k。我们还可以找到'book'字样:h b e o jll ok。唯一的限制是隐藏子字符串的字母必须在原始字符串中按正确顺序排列。我将如何在Python中实现这个?谢谢。

+0

你看过距离算法了吗? –

+0

@ IgnacioVazquez-Abrams没关系。我对此并不熟悉。 –

+0

我可能会通过获取单词列表(例如,在Ubuntu上的'/ usr/share/dict/words'上找到)并对它们逐个运行测试,返回匹配的单词... – Shadow

回答

2

循环查找单词中的每个字母,并从找到的最后一个字母开始在原始字符串中查找该字母。当找不到字母或没有更多字母要查找时返回结果。

def f(orig, word): 
    idx = 0 
    for letter in word: 
     x = orig.find(letter, idx) 
     if x != -1: 
      idx = x 
     else: 
      return False 
    return True 
+1

我有预计这会比正则表达式方法慢:'re.search('。*'。join(word),orig)不是None ... ...但实际上它更快。 +1 –