Last updated on January 7th, 2025 at 03:16 am

Here, we see the Word Break LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Dynamic Programming

Companies

Amazon, Bloomberg, Facebook, Google, Pocketgems, Uber, Yahoo

Level of Question

Medium

Word Break LeetCode Solution

1. Problem Statement

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

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is Dynamic Programming with Memoization. This pattern is commonly used to solve problems where the solution to a problem can be broken down into overlapping subproblems, and the results of these subproblems can be reused to avoid redundant computations.

In this case, the problem is to determine if a string s can be segmented into a space-separated sequence of one or more dictionary words. The solution involves breaking the problem into smaller subproblems (checking substrings of s) and using memoization or a DP table to store intermediate results.

3. Code Implementation in Different Languages

3.1 Word Break 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)};
    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;
        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();
  }
};

3.2 Word Break Java

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        return recWay1(s, wordDict);
    }

    boolean recWay2(String s, List<String> wordDict) {
        Boolean[] memo = new Boolean[s.length() + 1];
        return wordBreak2(s, new HashSet<>(wordDict), 0, memo);
    }
    boolean wordBreak2(String s, Set<String> wordDict, int k, Boolean[] memo) {
        int n = s.length();
        if (k == n) return true;
        if (memo[k] != null) return memo[k];
        for (int i=k + 1; i<=n; i++) {
            String word = s.substring(k, i);
            if (wordDict.contains(word) && wordBreak2(s, wordDict, i, memo)) {
                return memo[k] = true;
            }
        }
        return memo[k] = false;
    }
    boolean recWay1(String s, List<String> wordDict) {
        Boolean[] memo = new Boolean[s.length() + 1];
        return wordBreak(s, wordDict, 0, memo);
    }
    boolean wordBreak(String s, List<String> wordDict, int k, Boolean[] memo) {
        if (k == s.length()) {
            return true;
        }
        if (memo[k] != null) {
            return memo[k];
        }
        for (int i=0; i<wordDict.size(); i++) {
            String word = wordDict.get(i);
            if (s.startsWith(word, k)) {
                if(wordBreak(s, wordDict, k + word.length(), memo)) return memo[k] = true;
            }
        }          
        return memo[k] = false;
    }
}

3.3 Word Break JavaScript

var wordBreak = function(s, wordDict) {
    let n = s.length;
    let dp = new Array(n + 1).fill(false);
    dp[0] = true;
    let max_len = Math.max(...wordDict.map(word => word.length));
    for (let i = 1; i <= n; i++) {
        for (let j = i - 1; j >= Math.max(i - max_len - 1, 0); j--) {
            if (dp[j] && wordDict.includes(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
};

3.4 Word Break Python

class Solution(object):
    def wordBreak(self, s, wordDict):
        def construct(current,wordDict, memo={}):
            if current in memo:
                return memo[current]
            if not current:
                return True
            for word in wordDict:
                if current.startswith(word):
                    new_current = current[len(word):]
                    if construct(new_current,wordDict,memo):
                        memo[current] = True
                        return True
            memo[current] = False
            return False
        return construct(s,wordDict)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n² * m)	O(n + m)
Java	O(n * m * k)	O(n + m)
JavaScript	O(n² * m)	O(n + m)
Python	O(n * m * k)	O(n + m)

Here,
n: Length of the string s.
m: Number of words in the dictionary.
k: Average length of words in the dictionary.

• The problem is solved using Dynamic Programming with Memoization.
• The C++ and JavaScript implementations use a bottom-up DP approach, while the Java and Python implementations use a top-down recursive approach with memoization.
• The time complexity is primarily driven by the nested loops or recursive calls, while the space complexity is determined by the size of the dp array or memo dictionary.