Skip to content

139. Word Break 👍

Approach 1: Top-down w/ raw string

  • Time: $O(n^3)$
  • Space: $O(n^2 + \Sigma |\texttt{wordDict[i]}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  bool wordBreak(string s, vector<string>& wordDict) {
    return wordBreak(s, {wordDict.begin(), wordDict.end()}, {});
  }

 private:
  bool wordBreak(const string& s, const unordered_set<string>&& wordSet,
                 unordered_map<string, bool>&& mem) {
    if (wordSet.contains(s))
      return true;
    if (const auto it = mem.find(s); it != mem.cend())
      return it->second;

    // 1 <= prefix.length() < s.length()
    for (int i = 1; i < s.length(); ++i) {
      const string& prefix = s.substr(0, i);
      const string& suffix = s.substr(i);
      if (wordSet.contains(prefix) &&
          wordBreak(suffix, std::move(wordSet), std::move(mem)))
        return mem[s] = true;
    }

    return mem[s] = false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    return wordBreak(s, new HashSet<>(wordDict), new HashMap<>());
  }

  private boolean wordBreak(final String s, Set<String> wordSet, Map<String, Boolean> mem) {
    if (mem.containsKey(s))
      return mem.get(s);
    if (wordSet.contains(s)) {
      mem.put(s, true);
      return true;
    }

    // 1 <= prefix.length() < s.length()
    for (int i = 1; i < s.length(); ++i) {
      final String prefix = s.substring(0, i);
      final String suffix = s.substring(i);
      if (wordSet.contains(prefix) && wordBreak(suffix, wordSet, mem)) {
        mem.put(s, true);
        return true;
      }
    }

    mem.put(s, false);
    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def wordBreak(self, s: str, wordDict: list[str]) -> bool:
    wordSet = set(wordDict)

    @functools.lru_cache(None)
    def wordBreak(s: str) -> bool:
      """Returns True if s can be segmented."""
      if s in wordSet:
        return True
      return any(s[:i] in wordSet and wordBreak(s[i:]) for i in range(len(s)))

    return wordBreak(s)

Approach 2: Top-down w/ index

  • Time: $O(n^3)$
  • Space: $O(n^2 + \Sigma |\texttt{wordDict[i]}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  bool wordBreak(string s, vector<string>& wordDict) {
    return wordBreak(s, 0, {wordDict.begin(), wordDict.end()},
                     vector<int>(s.length(), -1));
  }

 private:
  // Returns true if s[i..n) can be segmented.
  bool wordBreak(const string& s, int i, const unordered_set<string>&& wordSet,
                 vector<int>&& mem) {
    if (i == s.length())
      return true;
    if (mem[i] != -1)
      return mem[i];

    for (int j = i + 1; j <= s.length(); ++j)
      if (wordSet.contains(s.substr(i, j - i)) &&
          wordBreak(s, j, std::move(wordSet), std::move(mem)))
        return mem[i] = 1;

    return mem[i] = 0;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    return wordBreak(s, 0, new HashSet<>(wordDict), new Boolean[s.length()]);
  }

  // Returns true if s[i..n) can be segmented.
  private boolean wordBreak(final String s, int i, Set<String> wordSet, Boolean[] mem) {
    if (i == s.length())
      return true;
    if (mem[i] != null)
      return mem[i];

    for (int j = i + 1; j <= s.length(); ++j)
      if (wordSet.contains(s.substring(i, j)) && wordBreak(s, j, wordSet, mem))
        return mem[i] = true;

    return mem[i] = false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def wordBreak(self, s: str, wordDict: list[str]) -> bool:
    wordSet = set(wordDict)

    @functools.lru_cache(None)
    def wordBreak(i: int) -> bool:
      """Returns True if s[i..n) can be segmented."""
      if i == len(s):
        return True
      return any(s[i: j] in wordSet and wordBreak(j)
                 for j in range(i + 1, len(s) + 1))

    return wordBreak(0)

Approach 3: Bottom-up

  • Time: $O(n^3)$
  • Space: $O(n^2 + \Sigma |\texttt{wordDict[i]}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  bool wordBreak(string s, vector<string>& wordDict) {
    const int n = s.length();
    const unordered_set<string> wordSet{wordDict.begin(), wordDict.end()};
    // dp[i] := true if s[0..i) can be segmented
    vector<bool> dp(n + 1);
    dp[0] = true;

    for (int i = 1; i <= n; ++i)
      for (int j = 0; j < i; ++j)
        // s[0..j) can be segmented and s[j..i) is in `wordSet`, so s[0..i) can
        // be segmented.
        if (dp[j] && wordSet.contains(s.substr(j, i - j))) {
          dp[i] = true;
          break;
        }

    return dp[n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    final int n = s.length();
    Set<String> wordSet = new HashSet<>(wordDict);
    // dp[i] := true if s[0..i) can be segmented
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;

    for (int i = 1; i <= n; ++i)
      for (int j = 0; j < i; ++j)
        // s[0..j) can be segmented and s[j..i) is in `wordSet`, so s[0..i) can
        // be segmented.
        if (dp[j] && wordSet.contains(s.substring(j, i))) {
          dp[i] = true;
          break;
        }

    return dp[n];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def wordBreak(self, s: str, wordDict: list[str]) -> bool:
    n = len(s)
    wordSet = set(wordDict)
    # dp[i] := True if s[0..i) can be segmented
    dp = [True] + [False] * n

    for i in range(1, n + 1):
      for j in range(i):
        # s[0..j) can be segmented and s[j..i) is in `wordSet`, so s[0..i) can
        # be segmented.
        if dp[j] and s[j:i] in wordSet:
          dp[i] = True
          break

    return dp[n]

Approach 4: Bottom-up (optimized)

  • Time: $O(n^3)$
  • Space: $O(n^2 + \Sigma |\texttt{wordDict[i]}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  bool wordBreak(string s, vector<string>& wordDict) {
    const int n = s.length();
    const int maxLength = getMaxLength(wordDict);
    const unordered_set<string> wordSet{wordDict.begin(), wordDict.end()};
    // dp[i] := true if s[0..i) can be segmented
    vector<int> dp(n + 1);
    dp[0] = true;

    for (int i = 1; i <= n; ++i)
      for (int j = i - 1; j >= 0; --j) {
        if (i - j > maxLength)
          break;
        // s[0..j) can be segmented and s[j..i) is in the wordSet, so s[0..i)
        // can be segmented.
        if (dp[j] && wordSet.contains(s.substr(j, i - j))) {
          dp[i] = true;
          break;
        }
      }

    return dp[n];
  }

 private:
  int getMaxLength(const vector<string>& wordDict) {
    return ranges::max_element(wordDict, ranges::less{},
                               [](const string& word) {
      return word.length();
    })->length();
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    final int n = s.length();
    final int maxLength = getMaxLength(wordDict);
    Set<String> wordSet = new HashSet<>(wordDict);
    // dp[i] := true if s[0..i) can be segmented
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;

    for (int i = 1; i <= n; ++i)
      for (int j = i - 1; j >= 0; --j) {
        if (i - j > maxLength)
          break;
        // s[0..j) can be segmented and s[j..i) is in the wordSet, so s[0..i)
        // can be segmented.
        if (dp[j] && wordSet.contains(s.substring(j, i))) {
          dp[i] = true;
          break;
        }
      }

    return dp[n];
  }

  private int getMaxLength(List<String> wordDict) {
    return wordDict.stream().mapToInt(String::length).max().getAsInt();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def wordBreak(self, s: str, wordDict: list[str]) -> bool:
    n = len(s)
    maxLength = len(max(wordDict, key=len))
    wordSet = set(wordDict)
    # dp[i] := True if s[0..i) can be segmented
    dp = [True] + [False] * n

    for i in range(1, n + 1):
      for j in reversed(range(i)):
        if i - j > maxLength:
          break
        # s[0..j) can be segmented and s[j..i) is in the wordSet, so s[0..i)
        # can be segmented.
        if dp[j] and s[j:i] in wordSet:
          dp[i] = True
          break

    return dp[n]