Daily 25/05/2024: [140. Word Break II](https://leetcode.com/problems/word-break-ii/)

# 1. Tóm tắt đề bài
Cho một chuỗi ```s``` và một từ điển gồm các chuỗi ```wordDict```, hãy thêm dấu cách vào ```s``` để xây dựng một câu trong đó mỗi từ là một từ hợp lệ trong từ điển. Trả lại tất cả các câu có thể có theo thứ tự bất kỳ .

Lưu ý rằng cùng một từ trong từ điển có thể được sử dụng lại nhiều lần trong quá trình phân đoạn.

#### Giới hạn
- $1 \le$ ```s.length``` $\le 20$
- $1 \le$ ```wordDict.length``` $\le 1000$
- $1 \le$ ```wordDict[i].length``` $\le 10$
- ```s``` và ```wordDict[i]``` chỉ bao gồm các chữ cái tiếng Anh viết thường.
- Tất cả các chuỗi ```wordDict``` không trùng nhau.
- Dữ liệu đầu vào được tạo theo cách sao cho độ dài của câu trả lời không vượt quá $10^5$

# 2. Tóm tắt lời giải

#### Phân tích
- Bài này thực tế để mọi người có thể rèn luyện đệ quy backtrack.
- Thật vậy, chúng ta sẽ xét một chuỗi ```s```, chẳng hạn và xét từng vị trí của nó rồi kiểm tra xem ```s[0->i]``` có phải từ trong từ điển không rồi tính bài toán con với chuỗi ```s[i+1 -> end]```.

# 3. Lời giải chi tiết
#### Thuật toán
- Từ phân tích thì kết quả là chúng ta có công thức đệ quy sau.
- Chúng ta có hàm đệ quy ```slice```, với tham số là chuỗi cần xử lý ```s```.
- Trường hợp cơ sở là s đã được giải quyết hoặc s rỗng.
- res là mảng chưa đáp án của s.
- Xét từng ```s[0->i]```. Nếu ```s[0->i]``` trong từ điển thì chúng ta chỉ cần thêm vào res chuỗi ```s[0->i] + " " +``` từng thằng trong mảng kết quả của bài toán con với ```s[i+1->end]```.
- Để kiểm tra ```s``` đã được giải quyết chưa tránh lặp lại thêm bước đệ quy thì dùng ```map C++``` hay ```dict python``` và các cấu trúc tương tự ở ngôn ngữ khác.

#### Code

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> List[str]:
        n: ỉnt = len(s)

        word_set = set(wordDict)

        m = {}

        def slice(s: str):
            if s in m: return m[s]
            if not s: return []

            res = []

            for i in range(1, len(s) + 1):
                if s[:i] in word_set:
                    right = slice(s[i:])

                    if right:
                        for x in right:
                            res.append(s[:i] + " " + x)
                    elif not s[i:]:
                        res.append(s[:i])
            m[s] = res
            return res
        
        return slice(s)

#### Độ phức tạp
$O(2^n)$.
# 4. Kết luận & gợi ý mở rộng
- Một bài cuối tuần nhẹ nhàng.

> Hãy dùng nghị lực và sự kiên trì để đánh bại mọi thứ.

###### #Hashtag: <span style='color: blue'>Binary Tree, Depth First Search</span>