Разбиение строки на последовательность слов

Недавно я наткнулся на следующий вопрос на собеседовании:

Учитывая входную строку и словарь слов, реализуйте метод, который разбивает входную строку на разделенную пробелами строку словарных слов, которые поисковая машина можно использовать для "Вы имели в виду?" Например, ввод «яблочного пирога» должен давать на выходе «яблочный пирог».

Кажется, я не могу найти оптимального решения в том, что касается сложности. Есть ли у кого-нибудь предложения, как это сделать эффективно?