LeetCode #139: Word Break

LeetCode Solutions

https://leetcode.com/problems/word-break/

To solve this problem, we can use a backtracking approach that checks all possible combinations of substrings that exist in the dictionary. We can use a recursive function that takes the index of the current character we are examining and a list that represents the current path we have taken to get to this point.

Here are the steps to solve the problem:

  1. Create a result list to store all the possible combinations of substrings that exist in the dictionary.
  2. Define a recursive function called backtrack that takes the index of the current character we are examining and a list that represents the current path we have taken to get to this point.
  3. Base case: If the index is equal to the length of the string, then we have found a valid combination of substrings. Append the current path to the result list.
  4. For each word in the dictionary, check if it matches the substring starting from the current index. If it does, append the word to the current path and call the backtrack function recursively with the index updated to the end of the current word.
  5. If none of the words in the dictionary match the current substring, return.
  6. Finally, iterate through the result list and check if any of the combinations match the input string.

Here’s the solution in Python:

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        res = []
        @lru_cache(list)
        def backtrack(ind, path):
            if ind == len(s):
                res.append("".join(path))
                return 
    
            for w in wordDict:
                if s.startswith(w, ind):
                    path.append(w)
                    backtrack(ind+len(w), path)
                    path.pop()

        backtrack(0, [])
        for i in res:
            if i == s:
                return True
        return False

Time and Space Complexity

The time complexity of this solution is O(n^2), where n is the length of the input string. This is because we are using a nested loop to check if each substring is in the dictionary. The space complexity is also O(n^2) because we are using memoization to cache the results of previous function calls.