Python의 단어 나누기 II

비어 있지 않은 문자열 s와 wordDict라는 사전이 있다고 가정하면 이 사전은 비어 있지 않은 단어 목록을 포함하고 s에 공백을 추가하여 각 단어가 다음과 같은 문장을 구성합니다. 유효한 사전 단어. 가능한 모든 문장을 찾아야 합니다. "appleraincoat" 및 사전은 ["app", "apple", "rain", "coat", "raincoat"]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 하나의 지도 메모 만들기

• solve라는 메소드를 정의하면 string과 wordDict가 필요합니다.

• s가 null이면 빈 목록을 반환합니다.

• 메모에 s가 있으면 -

  • 회신 메모[s]

• ret 배열 생성

• 범위 1에서 s 크기까지의 i에 대해

  • index 0에서 i – 1까지 s의 부분 문자열이 wordDict에 있는 경우

    • for j in solve(i에서 끝까지 s의 부분 문자열, wordDict)

    • p :=인덱스 0에서 i – 1까지 s의 부분 문자열, 공백과 j로 연결한 다음 왼쪽과 오른쪽에서 추가 공백 지우기 −

    • ret에 p 삽입

• 메모[s] :=ret

• 회신 메모[s]

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def wordBreak(self, s, wordDict):
      self.memo = {}
      wordDict = set(wordDict)
      return self.solve(s,wordDict)
   def solve(self,s, wordDict):
      if not s:
         return ['']
      if s in self.memo:
         return self.memo[s]
      ret = []
      for i in range(1,len(s)+1):
         if s[:i] in wordDict:
            for j in self.solve(s[i:],wordDict):
               ret.append((s[:i] + " " + j).strip())
      self.memo[s] = ret
      return self.memo[s]

ob = Solution()
print(ob.wordBreak("appleraincoat",["app","apple","rain","coat","rain coat"]))

입력

"appleraincoat"
["app","apple","rain","coat","raincoat"]

출력

['apple rain coat', 'apple raincoat']