## Similar Problems

Similar Problems not available

# Word Break - Leetcode Solution

LeetCode: Word Break Leetcode Solution

Difficulty: Medium

Topics: string hash-table dynamic-programming array

Problem Statement:

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

- The same word in the dictionary may be reused multiple times in the segmentation.
- You may assume the dictionary does not contain duplicate words.

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

Solution:

Approach:

- We need to use dynamic programming to solve this problem.
- We will create a boolean array dp[] of size n+1, where n is the length of the given string s.
- Initially, all the elements of the dp[] array will be false.
- dp[i] will be true if the substring s[0, i) can be segmented into words present in the dictionary.
- To fill the dp[] array, we will iterate the string s from the left and for each substring s[0, i) check if there is any j (where 0 <= j < i) such that dp[j] is true and s[j, i) is present in the dictionary.

Step by Step solution:

- Initialize a hashset to store all the words in the dictionary so that lookups can be done efficiently.
- Initialize a boolean array dp of size n+1, where n is the length of the input string s.
- Fill the first element of the dp array with true, as an empty string can always be segmented.
- Iterate the string s from the first index to the last index.
- For each substring s[0, i), iterate from 0 to i.
- If dp[j] is true and s[j, i) is present in the dictionary, then mark dp[i] as true.
- Finally, return the value of dp[n], where n is the length of the input string s.

Time Complexity:

- The time complexity of this solution is O(n^2), where n is the length of the input string.
- We are iterating over the string twice, once to fill the boolean array dp and once to check for each substring if there is a split point or not.
- Lookup in the hashset is constant time, so it does not contribute to the time complexity.

Space Complexity:

- The space complexity of this solution is O(n), where n is the length of the input string.
- We are using a boolean array dp of size n+1.

Code:

Here's the Python implementation of the above approach.

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

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

## Word Break Solution Code

`1`