LeetCode 139: Word Break Solution

Master LeetCode problem 139 (Word Break), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

139. Word Break

Medium

Array Hash Table String Dynamic Programming Trie Memoization

Problem Explanation

Explanation

To solve this problem, we can use dynamic programming. We will create a boolean array dp of size s.length() + 1, where dp[i] will be true if the substring s[0:i] can be segmented into words from the dictionary. We iterate over the string s and at each position, we check if any prefix of the current substring is in the dictionary and if the remaining suffix is also part of the segmented words.

Algorithm:

Initialize a boolean array dp of size s.length() + 1 where dp[i] indicates if the substring s[0:i] can be segmented into words from the dictionary.
Set dp[0] = true since an empty string can be segmented.
Iterate over the string s and at each position i, iterate from 0 to i to check if any prefix of the current substring is in the dictionary and if the remaining suffix is also part of the segmented words.
Update dp[i] if the current substring can be segmented.
Return dp[s.length()].

Time Complexity:

The time complexity of this solution is O(n^2) where n is the length of the input string s.

Space Complexity:

The space complexity of this solution is O(n) where n is the length of the input string s.

Solution Code

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> dict = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[s.length()];
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 139 (Word Break)?

This page provides optimized solutions for LeetCode problem 139 (Word Break) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 139 (Word Break)?

The time complexity for LeetCode 139 (Word Break) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 139 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 139 in Java, C++, or Python.

Back to LeetCode Solutions