Fixing a brute force algorithm solution

Fixing a brute force algorithm solution


Google has a video coaching job candidates on whiteboarding.

In it, they provide a sample problem (given a string of two words without spaces and a dictionary of valid words, return a string with the same words appropriately separated by a space).

They also provide a sample solution and one of the coaches explains that one easy way to improve the solution is to make it not a brute-force solution. See a few seconds into the video here:

I don’t understand how this solution can be improved, including how it can be improved by somehow not making it not “brute force”.

Can anyone explain?


I’m no whiz at these things myself. I’ve not gotten any good at actually solving these, but I can identify this either as a DP or backtracking algorithm question.

So the less brute force way probably involves some sort of memorization/recursion. Like recursively checking whether substring is made up of valid words or remembering where the last valid substrings position is and all the proper spaces before it.

I can’t really come up with an implementation on the spot, but that’s probably what they mean by less brute force way