문자열이 다른 문자열과 연결되어 있는지 찾기

Question

문자열이 다른 문자열 (이 문자열은 연결 문자열에서 반복 될 수 있음)의 연결인지 여부를 결정해야하는 문제에 대해 작업 중입니다. 나는 가능한 한 효율적으로 역 추적을 사용하고 있습니다. 문자열이 연결이면 문자열의 연결을 인쇄합니다. 그렇지 않으면 NOT POSSIBLE이 인쇄됩니다. 다음은 파이썬 코드입니다.

# 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) 

필자는 테스트 케이스의 마지막 부분을 계속 실패하고 그 이유를 알 수 없습니다. 누군가가 실패 할 경우를 대비하여 올바른 방향으로 나를 안내 할 수 있습니까? 감사!

Answer 1

우선,이 코드는 복잡하지 않습니다. 예를 들어, 여기에 상응하는, 짧은 용액이다

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'