2017-03-15 194 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 –