查找字符串是否與其他字符串連接

我正在處理一個問題，即必須確定一個字符串是否是其他字符串的連接（這些字符串可以在連接字符串中重複）。我正在使用回溯來儘可能高效。如果字符串是串聯的，它將打印它串聯的字符串。如果沒有，它將打印NOT POSSIBLE。這裏是我的Python代碼：查找字符串是否與其他字符串連接

# note: strList has to have been sorted 
def findFirstSubstr(strList, substr, start = 0): 
    index = start 
    if (index >= len(strList)): 
     return -1 
    while (strList[index][:len(substr)] != substr): 
     index += 1 
     if (index >= len(strList)): 
      return -1 
    return index 


def findPossibilities(stringConcat, stringList): 
    stringList.sort() 
    i = 0 
    index = 0 
    substr = '' 
    resultDeque = [] 
    indexStack = [] 
    while (i < len(stringConcat)): 
     substr += stringConcat[i] 
     index = findFirstSubstr(stringList, substr, index) 
     if (index < 0): 
      if (len(resultDeque) == 0): 
       return 'NOT POSSIBLE' 
      else: 
       i -= len(resultDeque.pop()) 
       index = indexStack.pop() + 1 
       substr = '' 
       continue 
     elif (stringList[index] == substr): 
      resultDeque.append(stringList[index]) 
      indexStack.append(index) 
      index = 0 
      substr = '' 
     i += 1 
    return ' '.join(resultDeque)

我把失敗的測試用例的後半段，不能找出原因。有人會提示我在任何情況下都會失敗嗎？謝謝！

來源

2017-05-17 theEpsilon

FYI：如果你需要一個deque，使用['collections.deque']（https://docs.python.org/3/library/collections.html#collections.deque）中的'deque'類。 –

@ChristianDean謝謝你的建議。我是Python新手，只是使用列表，因爲我知道的就是 – theEpsilon

是的，我想我可能會提到它，因爲你說你在尋找速度。因爲它是一個專用的deque，它將比標準的Python列表更快（當然，你會像使用deque一樣）。 –

首先，這個代碼是不必要的複雜。例如，下面是等效的，但是較短的解決方案：

def findPossibilities(stringConcat, stringList): 
    if not stringConcat: # if you want exact match, add `and not stringList` 
     return True 

    return any(findPossibilities(stringConcat[len(s):], 
           stringList[:i] + stringList[i+1:]) # assuming non-repeatable match. Otherwise, simply replace with `stringList` 
       for i, s in enumerate(stringList) 
       if stringConcat.startswith(s))

實際答案：

邊界條件：的stringConcat其餘部分相匹配的一些stringList，停止搜索：

>>> findPossibilities('aaaccbbbccc', ['aaa', 'bb', 'ccb', 'cccc']) 
'aaa ccb bb'

來源

2017-05-17 04:27:30 Marat

這將花費我一點，通過您的代碼排序，但upvoting邊界條件 – theEpsilon

查找字符串是否與其他字符串連接

回答

相關問題