#139

Word Break

specialist · 880 · lc medium +31 · verified · 49.2% accepted · 18,608 likes · top 36%

Description

Given a string s and a dictionary wordDict, determine whether s can be segmented into a space-separated sequence of words all drawn from wordDict. Return true if possible.

Words from the dictionary may be reused any number of times.

Example 1:

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

Output: true

Explanation: Return true because "leetcode" can be segmented as "leet code".

Example 2:

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

Output: true

Explanation: Return true because "applepenapple" can be segmented as "apple pen apple".

Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]

Output: false

Code

1

2

3

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool: