139. Word Break

Problem Statement

link: https://leetcode.com/problems/word-break/ https://leetcode.cn/problems/word-break/

Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example:

Input: s = "leetcode", wordDict = ["leet","code"] Output: true

Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true

Solution Approach

Utilize dynamic programming to determine if substrings can be formed using dictionary words.

Algorithm

1. Initialization: Create a boolean array dp with a length of string s plus one and initialize the first element to True.
2. Substrings Check: For each substring ending at index i, check if the substring matches any word in the dictionary and if the previous substring is also valid (indicated by dp).
3. Final Check: The last element of the dp array indicates whether the whole string can be segmented using dictionary words.

Implement

    class Solution:
      def wordBreak(self, s: str, wordDict: List[str]) -> bool:
          n = len(s)
          dp = [False] * (n + 1)
          dp[0] = True
          for i in range(1, n + 1):
              for word in wordDict:
                  l = len(word)
                  if i >= l and s[i - l: i] == word and dp[i - l]:
                      dp[i] = True
                      break
          return dp[n]

    
    

Twitter  facebook  Email