Word break using memoization – Code

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, which helps to improve complexity.

Memoization is one of Dynamic programming(DP) techniques. DP is able to solve a complex problem by breaking it down into sub-problems. Each following steps can re-use the result from the previous steps, and avoid redundant calculations or operations. This improves the time complexity significantly, from exponential to O(n^3) or O(n^2).

How to use memoization in word break?

Declare a variable (called memo) in dfs wrapper method. Its data structure is list or set. Add this variable as one input parameter of dfs helper (recursive) method. At the beginning of the helper method, check whether the input is stored in memo. if it is, return memo value directly. Within the body of helper method, update the memo value before call itself.Word break feature

Amazon Interview Question:
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.





shortest path bfs doodle

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)

Download WordBreak.java
Download WordBreak.js
Download WordBreak.py
Java Coding Interview Pocket Book

Comments are closed