Word Break - Leetcode Solution

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]

1