Leetcode

Word Break

May 26, 2022 by aAshish

Approach 1: Top-down w/ raw string

  • Time:O(n^3)
  • Space:O(n^2 + \Sigma |\texttt{wordDict[i]}|)

C++

 
class Solution {
 public:
  bool wordBreak(string s, vector<string>& wordDict) {
    return wordBreak(s, {begin(wordDict), end(wordDict)}, {});
  }

 private:
  bool wordBreak(const string& s, const unordered_set<string>&& wordSet,
                 unordered_map<string, bool>&& memo) {
    if (wordSet.count(s))
      return true;
    if (memo.count(s))
      return memo[s];

    // 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.count(prefix) && wordBreak(suffix, move(wordSet), move(memo)))
        return memo[s] = true;
    }

    return memo[s] = false;
  }
};

JAVA

 
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> memo) {
    if (memo.containsKey(s))
      return memo.get(s);
    if (wordSet.contains(s)) {
      memo.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, memo)) {
        memo.put(s, true);
        return true;
      }
    }

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

Python

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

    @lru_cache(None)
    def wordBreak(s: str) -> bool:
      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]}|)

C++

 
class Solution {
 public:
  bool wordBreak(string s, vector<string>& wordDict) {
    return wordBreak(s, 0, {begin(wordDict), end(wordDict)},
                     vector<int>(s.length(), -1));
  }

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

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

    return memo[i] = 0;
  }
};

JAVA

 
class Solution {
  public boolean wordBreak(String s, List<String> wordDict) {
    return wordBreak(s, 0, new HashSet<>(wordDict), new Boolean[s.length()]);
  }

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

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

    return memo[i] = false;
  }
}

Python

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

    @lru_cache(None)
    def wordBreak(i: int) -> bool:
      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]}|)

C++

 
class Solution {
 public:
  bool wordBreak(string s, vector<string>& wordDict) {
    const int n = s.length();
    unordered_set<string> wordSet{begin(wordDict), end(wordDict)};
    // 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) in wordSet
        // so s[0..i) can be segmented
        if (dp[j] && wordSet.count(s.substr(j, i - j))) {
          dp[i] = true;
          break;
        }

    return dp[n];
  }
};

JAVA

 
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) 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];
  }
}

Python

 
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) 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]}|)

C++

 
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{begin(wordDict), end(wordDict)};
    // 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) in wordSet
        // so s[0..i) can be segmented
        if (dp[j] && wordSet.count(s.substr(j, i - j))) {
          dp[i] = true;
          break;
        }
      }

    return dp[n];
  }

 private:
  int getMaxLength(const vector<string>& wordDict) {
    return max_element(begin(wordDict), end(wordDict),
                       [](const auto& a, const auto& b) {
                         return a.length() < b.length();
                       })
        ->length();
  }
};

JAVA

 
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) 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];
  }

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

Python

 
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) 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]