Учитывая непустую строку 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 для решения этой проблемы, не забудьте кэшировать повторно используемые строки.