Как разбить данный текст на слова из словаря?

Это вопрос из интервью. Предположим, у вас есть строка текст и словарь (набор строк). Как разбить текст на подстроки так, чтобы каждая подстрока находилась в словаре .

Например, вы можете разбить "thisisatext" на ["this", "is", "a", "text"] с помощью / usr / share / dict / words .

Я считаю, что обратное отслеживание может решить эту проблему (в псевдо-Java):

void solve(String s, Set<String> dict, List<String> solution) {
   if (s.length == 0)
      return
   for each prefix of s found in dict
      solve(s without prefix, dict, solution + prefix)
}

List<String> solution = new List<String>()
solve(text, dict, solution)

Есть ли в этом смысл? Вы бы оптимизировали шаг поиска префиксов в словаре? Какие структуры данных вы бы порекомендовали?