educative.io

Word Brea solution with memoization

Courses
,
#1

Hello,

It is mentioned at the bottom of the word brea problem that use a set to avoid duplicate calls. I implemented the solution from this feedback, but no improvement in time complexity.
Could you check if I implemented it right?

class Solution {
public boolean wordBreak(String s, List wordDict) {
HashSet deadEnd = new HashSet<>();

  for (int i = 1; i <= s.length(); ++i) {
  String first = s.substring(0, i);
  if (wordDict.contains(first)) {
    String second = s.substring(i);

    if(!deadEnd.contains(second)){
    if (second == null || second.length() == 0 || wordDict.contains(second) || wordBreak(second, wordDict)) {
      return true;
    }else{
        deadEnd.add(second);
    }

  }
  }
}
return false;
}

}

#2

Hi Seb,

This is Hamza from Educative.

The word-break challenge will in fact result in a better time and space complexity if we use memoization. This happens because no extra recursive function call is made for a substring that has already been tested once. This condition is ensured by the extra if condition that is added, which verifies if the substring has already been checked. Therefore, we can save a lot of time by ignoring repetitive function calls. This will also save a lot of memory too since each recursive function call takes its own space in the memory.

As for your solution, what raises doubts regarding you being unsure about the time and space complexity not being affected? If you are basing your assumption simply on the execution time of this code and the solution that does not use memoization, then that would not be a valid way to determine any improvements. The problem is a very small scale problem and you won’t notice any difference for such a small example.

please do share any other confusion that you might have regarding this challenge or any other lesson or course so we can help you out the best way possible.

We hope Educative has inspired to further your learning.

Best Regards,
Hamza | Developer Advocate

1 Like