Word Break II

Sizga s satri va lug'at vazifasini bajaruvchi, so'zlardan iborat bo'lgan wordDict massivi berilgan.

Siz s satrining ichiga shunday bo'shliqlar (space) qo'shishingiz kerakki, hosil bo'lgan har bir jumla to'liq wordDict dagi so'zlardan tashkil topgan bo'lsin. Barcha mumkin bo'lgan to'g'ri jumlalar ro'yxatini qaytaring. Natijani istalgan tartibda qaytarish mumkin.

Lug'atdagi so'zlar jumla ichida takrorlanishi mumkin.

func solve(s string, wordDict []string) []string {
    // ...
}

Misollar

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

Input: s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple", "pine applepen apple", "pineapple pen apple"]

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

Maslahatlar

1. Bu backtracking (rekursiya) masalasi, lekin bir xil pozitsiyadan boshlangan qidiruv bir necha marta takrorlanib ketishi mumkin — natijalarni pozitsiya bo'yicha keshlab (memoizatsiya) qo'ying, shunda har bir pozitsiya faqat bir marta qayta ishlanadi.
2. dfs(start) funksiyasi "s[start:] dan hosil bo'ladigan barcha mumkin jumlalar ro'yxati"ni qaytarsin. Har bir end (start+1 dan len(s) gacha) uchun s[start:end] lug'atda bormi tekshiring, bo'lsa dfs(end) ni chaqirib qolgan qismning barcha variantlarini oling va joriy so'z bilan birlashtirib natijaga qo'shing (qolgan qism bo'sh bo'lsa faqat so'zning o'zini qo'shing); start==len(s) bo'lganda bazaviy holat sifatida bitta bo'sh jumla qaytaring.