Word Break

---

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.

---

Try this Problem on your own or check similar problems:

1. Word Break II

Solution:

Java

public boolean wordBreak(String s, List<String> wordDict) {
  int n = s.length();
  boolean[] dp = new boolean[n+1];
  dp[0] = true;

  Set<String> dict = new HashSet<String>(wordDict);

  for(int i = 0; i < n; ++i){
      for(int j = i; j >= 0; --j){
          if(dp[j] && dict.contains(s.substring(j, i+1))){
              dp[i+1] = true;
          }
      }
  }

  return dp[n];
}

JavaScript

/**
 * @param {string} s
 * @param {string[]} wordDict
 * @return {boolean}
 */
var wordBreak = function (s, wordDict) {
  const n = s.length;
  const dp = new Array(n + 1).fill(false);
  dp[0] = true;

  const dict = new Set(wordDict);

  for (let i = 0; i < n; i++) {
    for (let j = i; j >= 0; j--) {
      if (dp[j] && dict.has(s.substring(j, i + 1))) {
        dp[i + 1] = true;
      }
    }
  }

  return dp[n];
};

Python

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True

        dict_set = set(wordDict)

        for i in range(n):
            for j in range(i, -1, -1):
                if dp[j] and s[j:i+1] in dict_set:
                    dp[i + 1] = True
                    break

        return dp[n]

C++

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.length();
        std::vector<bool> dp(n + 1, false);
        dp[0] = true;

        std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());

        for (int i = 0; i < n; i++) {
            for (int j = i; j >= 0; j--) {
                if (dp[j] && dict.count(s.substr(j, i - j + 1))) {
                    dp[i + 1] = true;
                    break;
                }
            }
        }

        return dp[n];
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n^3)
• Space Complexity: O(n)

---

Explanation:

First, we must make retrieving info whether a word is in the wordDict faster, to do that we create a set and put all words in it. Then for each character (in the outer loop) we check if it can form word with characters before it (inner loop) such that the word starting at j and ending at current character at index i exists in our set dict and there is an existing breakdown of all other words before our new word such that each word exists in the set. To track this breakdown, we need a dp helper array which keeps track if there is a valid breakdown of the words up until character at index i. Notice that dp is shifted by one place, since there is always a valid breakdown of an empty string. We get O(n^2) because of the loop and the additional multiplier n because of string comparison hashing when checking if the word exists in the dict.