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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
import java.util.*; public class WordBreak { //Wrapper, Time O(s^3), Space O(s^2) public static int wordBreak(String str, List<String> dict) { List<String> list = helper(str.toLowerCase(), dict, new HashMap<String, List<String>>()); System.out.println(list); return list.size(); } //DFS + memoization, Time worst O(2^s) average O(s^2*w) ~ O(s^3) //when memoziation takes places, extra loop to copy output //Space O(s^2), s is input string length, w is max length of words in dictionary private static List<String> helper(String s, List<String> dict, Map<String, List<String>> memo) { if (memo.containsKey(s)) //use memoization to limit overlap process return memo.get(s); List<String> res = new ArrayList<String>(); for (String w : dict) { if (s.startsWith(w)) { String next = s.substring(w.length()); if (next.length() == 0) res.add(w); else { for (String sub : helper(next, dict, memo)) res.add(w + " " + sub); } } } memo.put(s, res); //save partial results return res; } public static void main(String[] args) { List<String> words = Arrays.asList( "cat", "cats","dog", "dogs", "and", "sand", "scare", "eats", "eat", "care"); //Test case 1 String s = "dogeatscare"; System.out.println("Input: " + s); System.out.println("Word break count: " + wordBreak(s, words)); System.out.println(); //Test case 2 String s1 = "catsanddogs"; System.out.println("Input: " + s1); System.out.println("Word break count: " + wordBreak(s1, words)); } } |
Output:
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)
Note:
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.
Actionable:
Download WordBreak.java
Word break using memoization tutorial
The complete list of coding interview questions
