Fixing a brute force algorithm solution

Career Advice
1

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?

2

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