Word break#

Levels: level-4

Data structures: string

Algorithms: dynamic-programming

Practice Link#

LeetCode

Description#

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.

Examples#

1Input: s = "leetcode", wordDict = ["leet", "code"]
2Output: true
3Explanation: Return true because "leetcode" can be segmented as "leet code".

1Input: s = "applepenapple", wordDict = ["apple", "pen"]
2Output: true
3Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".
4             Note that you are allowed to reuse a dictionary word.

1Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
2Output: false

Python Solution#

 1class Solution(object):
 2    def wordBreak(self, s, wordDict):
 3        """
 4        :type s: str
 5        :type wordDict: Set[str]
 6        :rtype: bool
 7        """
 8        # dp[i] means s[:i+1] can be segmented into words in the wordDicts
 9        dp = [False] * (len(s) + 1)
10        dp[0] = True
11        for i in range(len(s)):
12            if dp[i]:
13                for j in range(i, len(s)):
14                    if s[i:j + 1] in wordDict:
15                        dp[j + 1] = True
16
17        return dp[-1]