LeetCode #139 Word Break

Medium

Problem

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.

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

Solution — DFS

It’s trivial that we can use DFS approach to solve this problem. But sadly, it will reach time limitation of LeetCode.

Complexity

It’s too hard for me to compute time/space complexity of this approach because the calling stack is hard to estimate. If you know how to estimate it, please let me know. Thanks a lot.

Solution — Dynamic Programming

At each character of the given string, we can check substrings that we visited before to know if the substring that end at current index is also a break.

Complexity

It’s clear that nested two loops take O(n²) time if we assume checking existence in wordDict only take O(1) time. And it’s trivial that we need O(n) extra space for the dp list.