Microsoft Interview Question
Software Engineer / DevelopersTeam: MS Office Platform
Country: India
Interview Type: In-Person
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.
dyanamic programming word-break-problem
- user1011 June 04, 2014