Daily 2/9/2023: [2707. Extra Characters in a String](https://leetcode.com/problems/extra-characters-in-a-string/?envType=daily-question&envId=2023-09-02)

# 1. Tóm tắt đề bài
Bạn được cung cấp một chuỗi **s** và một từ điển các từ **dictionary**. Bạn phải chia **s** thành một hoặc nhiều chuỗi con không chồng chéo sao cho mỗi chuỗi con đều có trong từ điển. Có thể có một số ký tự phụ trong **s** không có trong bất kỳ chuỗi con nào.

Trả về số ký tự thừa tối thiểu còn sót lại nếu bạn chia **s** một cách tối ưu.
#### Lưu ý
- **dictionary[i]** và **s** chỉ chứa chữ cái thường
- **dictionary** chứa các từ riêng biệt

#### Giới hạn
- $1 \le s.length \le 50$
- $1 \le dictionary.length \le 50$
- $1 \le dictionary[i].length \le 50$

# 2. Tóm tắt lời giải
#### Cách tiếp cận
Với dạng bài này mà giới hạn lại khá nhỏ chúng ta có thể nghĩ đến cách dụng đệ quy có nhớ. Bài toán con của chung ta đơn giản là tìm số lượng kí tự thừa ở vị trí **j** từ cuối lên.
Tuy nhiên chúng ta có thể dùng quy hoạch động để lời giải trơn tru hơn.

# 3. Lời giải chi tiết
#### Thuật toán
- **n** là độ dài chuõi **s**
- Xây dựng mảng dp có độ dài **n + 1** với **dp[i]** là số kí tự thừa tối thiểu khi xét **i** phần tử đầu của **s**.
- Duyệt **i** lần tượt từ **1** tới **n**. Để mặc định $dp[i] = dp[i - 1]$ (trường hợp kí tự đang xét cũng thừa)
- Lần lượt xét **length** chạy từ không tới i, kiểm tra substring từ **i - length** đến **i** có trong dictionary không. Nếu có thì $dp[i] = min(dp[i - length], dp[i])$
- Trả về $dp[n]$

#### Code

class Solution:
    def minExtraChar(self, s: str, dictionary: List[str]) -> int:
        n = len(s)
        
        dp = [0] * (n + 1)
        
        for i in range(1, n + 1):
            dp[i] = dp[i - 1] + 1

            for length in range(i + 1):
                if s[i - length: i] in dictionary:
                    dp[i] = min(dp[i - length], dp[i])

        return dp[-1]

#### Độ phức tạp
$O(n^2 * m)$ với **n** là độ dài của chuỗi s và **m** là số lượng từ trong từ điển,
# 4. Kết luận & gợi ý mở rộng
- Đây là một dạng bài toán quy hoạch động cơ bản tuy nhiên đỏi hỏi một chút kĩ thuật về chuỗi. Với code **python** thì khá tiện lợi ở việc lấy ra **substring** và kiểm tra trong mảng **dictionary** một cách ngắn gọn, còn các ngôn ngữ khác như **C++** thì cần xử lý lần lượt các bước theo thứ tự.
- Chúng ta có một cách tối ưu hơn để kiểm tra **substring** trong **dictionary** đó là sử dụng cấu trúc dữ liệu [Trie](https://vnoi.info/wiki/algo/data-structures/trie.md). Mời bạn đọc có thể tìm hiểu thêm.

- Bài tập tương tự.
[139. Word Break](https://leetcode.com/problems/word-break/)

###### Hashtag: <span style='color: blue'> dynamic programing, trie </span>