Word break using memoization – Code

What is word break? Word break is to divide a string into sub-strings that defined in dictionary. The problem is usually solved with recursion. The time complexity is exponential. Here we introduce word break using memoization.

Memoization is one of Dynamic programming(DP) technique. DP is able to solve a complex problem by breaking it down into sub-problems.

The approach of using memoization is:

1. First solve the problem with recursion. This consists of a wrapper method and a helper method. The wrapper method define the initial input and output, then call helper. The helper method is a recursion function which solves sub-problem.

2. Next is to add memoization variable. Declare a variable (called memo) in wrapper method. The data structure is often list or set. Add this variable as one input parameter of helper method. At the beginning, check whether the input is stored in memo. if it is, return memo value directly. This improves the time complexity significantly, from exponential to O(n^3) or O(n^2) .

Amazon Interview Question (CareerCup):
How would you like to efficiently find the total number of possible ways with which given string may be converted to whole dictionary words.
Example :
String = “Dogeatscare”
possible combinations – “Dog, eat, scare ” and “Dog, eats, care”
output is 2.

Java Code:

Input: dogeatscare
[dog eats care, dog eat scare]
Word break count: 2

Input: catsanddogs
[cat sand dogs, cats and dogs]
Word break count: 2

O Notation:

Recursion with memoization:
Time complexity: O(s^3)
Space complexity: O(s^2)

If you have any questions or want to put comments, please post at youtube. I will answer you!
The code displayed here is the improved version after the enhancement in the 2nd edition of Java coding interview pocket book.

Download WordBreak.java
Word break using memoization tutorial
The complete list of coding interview questions

Comments are closed