Учитывая непустую строку s и словарь wordDict, содержащий список непустых слов, добавьте пробелы в s, чтобы составить предложение, в котором каждое слово является допустимым словарным словом. Верните все такие возможные предложения.

Примечание.

  • Одно и то же слово в словаре может многократно использоваться при сегментации.
  • Вы можете предположить, что словарь не содержит повторяющихся слов.

Пример 1:

Input:
s = "catsanddog"
wordDict = ["cat", "cats", "and", "sand", "dog"]
Output:
[
  "cats and dog",
  "cat sand dog"
]

Пример 2:

Input:
s = "pineapplepenapple"
wordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
Output:
[
  "pine apple pen apple",
  "pineapple pen apple",
  "pine applepen apple"
]
Explanation: Note that you are allowed to reuse a dictionary word.

Пример 3:

Input:
s = "catsandog"
wordDict = ["cats", "dog", "sand", "and", "cat"]
Output:
[]

Используйте DFS для решения этой проблемы, не забудьте кэшировать повторно используемые строки.