:orphan:

Word Break
==========

.. highlight:: none

Problem
-------
https://leetcode.com/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 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

 

**Constraints:**

- ``1 <= s.length <= 300``
- ``1 <= wordDict.length <= 1000``
- ``1 <= wordDict[i].length <= 20``
- ``s`` and ``wordDict[i]`` consist of only lowercase English letters.
- All the strings of ``wordDict`` are **unique**.

.. highlight:: python

Pattern
-------
Array, Hash Table, String, Dynamic Programming, Trie

Approaches
----------

.. tab-set::

    .. tab-item:: Memoization

        **Code**

        .. literalinclude:: ../problems/medium/word-break/word_break__memoization.py
            :language: python
            :lines: 12-

        **Test**

        >>> from word_break__memoization import wordBreak
        >>> wordBreak("leetcode", ["leet", "code"])
        True
        >>> wordBreak("applepenapple", ["apple", "pen"])
        True
        >>> wordBreak("catsandog", ["cats", "dog", "sand", "and", "cat"])
        False

        .. autofunction:: word_break__memoization.wordBreak