CareerCup

dyanamic programming word-break-problem

Lets say the string has N characters and we can search a substring from positions i to j in the dictionary in O(1) using the given function.

a) Create a boolean array V of size N and initialize its elements to false, except V[N] = true. Traverse the positions from end to beginning. V[i] will be true if we can reach position N from position i. We check all positions j (j > i) such that characters i..j-1 form a word from the dictionary. If V[j] is true, so is V[i]. The text can be converted if we reach position N. The time complexity is O(N^2). Space complexity is O(N).

b) Very similar to a) except that V will count the number of ways we can reach position N from i. V[N] is 1 and we sum the number of ways, V[j], for each valid j > i. The time complexity is O(N^2). Space complexity is O(N).

c) Very similar to b) except that we don't sum, but take the minimum. V[i] = min(V[j]+1) for all valid j or infinity if there is no valid j.

d) Save in an additional array Next the index of the minimum for each position.

e) Traverse Next, starting from 0 and jumping to the next position.

1) Greedy approaches will take a local optimum and may fail to find an existing solution. Simple example: string = "aab", dict = {"a", "aa", "ab"}. There is a solution "a ab" but the most common greedy algorithm will pick "aa" first and not find a solution because there is no "b" in dict.

2) Backtracking works but is extremely slow. There are 2^N possible splits and it would explore them all, yielding a O(2^N) solution.

Solution for c) part of the problem