파이썬에서 단어 나누기

비어 있지 않은 문자열 s와 사전 wordDict가 있다고 가정합니다. 비어 있지 않은 단어 목록을 포함하는 경우 s가 공백으로 구분된 하나 이상의 사전 단어 시퀀스로 분할될 수 있는 시점을 결정합니다. 우리는 몇 가지 규칙을 따라야 합니다 -

• 사전의 동일한 단어는 분할에서 여러 번 재사용될 수 있습니다.
• 사전에 중복되는 단어가 없다고 가정할 수 있습니다.

문자열 s ="applepenapple"이고 단어 사전이 ["apple", "pen"]과 같다고 가정하면 문자열 s가 "apple pen apple"로 분할될 수 있기 때문에 출력은 true가 됩니다.

단계를 살펴보겠습니다 -

• n x n차의 행렬 DP 하나를 정의합니다. n =문자열의 크기, false로 초기화
• 범위 1에서 s
  까지의 i에 대해
  • 0에서 s까지의 범위에 있는 j의 경우 – i
    • 사전의 부분 문자열 s[j to j + 1]이면 dp[j, j+i - 1] :=True
    • 그렇지 않으면
      • j + 1 ~ j + i
        범위의 k에 대해
        • dp[j, k - 1] 및 dp[k, j + i – 1]이면 dp[j, j + i – 1] :=True
• 반환 DP[0, 길이 s - 1]

예시(파이썬)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

class Solution(object):
   def wordBreak(self, s, wordDict):
      dp = [[False for i in range(len(s))] for x in range(len(s))]
      for i in range(1,len(s)+1):
         for j in range(len(s)-i+1):
            #print(s[j:j+i])
            if s[j:j+i] in wordDict:
               dp[j][j+i-1] = True
            else:
               for k in range(j+1,j+i):
                  if dp[j][k-1] and dp[k][j+i-1]:
                     dp[j][j+i-1]= True
      return dp[0][len(s) - 1]
ob1 = Solution()
print(ob1.wordBreak("applepenapple", ["apple", "pen"]))

입력

"applepenapple"
["apple", "pen"]

출력

true