# LeetCode 2707. Extra Characters in a String

https://leetcode.com/problems/extra-characters-in-a-string/description/

## 題目大意

給你字串 `s` 跟一個陣列 `dictionary` 裡面裝一堆字串

我們要盡量把 `s` 不重疊地拆成 `dictionary` 裡面的詞

`s` 中可能有多餘的字，試問最少會剩多少多餘的字

## 思考

這題我們顯然可以使用 DP 來解

我們定義 $dp[i]$ 為 $s[i...n-1]$ 這段子字串的最小多餘字符數
並且我們額外定義 $dp[n] = 0$

若 $s[i]$ 為多餘的字符，則顯然 $dp[i] = dp[i+1] + 1$

另一種情況是我們在 `dictionary` 中找到某個長度為 $l$ 的詞 `word` 使得 $s[i...i+l-1]$ 這個子字串與 `word` 匹配
則此時 $dp[i] = dp[i+l]$ (表示剩餘字符都在 $s[i+l...n-1]$ 故最小多於字符等於 $dp[i+l]$)

故得到下列遞迴式：

$$
dp[i] = \min \left\{ dp[i+1]+1 , dp[i+l] \right\}
$$

class Solution
{
public:
    int minExtraChar(string s, vector<string> &dictionary)
    {
        int n = s.size();

        vector<int> dp(n + 1);

        for (int i = n - 1; i >= 0; --i)
        {
            dp[i] = dp[i + 1] + 1;

            for (const string &word : dictionary)
            {
                const int len = word.size();
                if (i + len <= n && memcmp(s.data() + i, word.data(), len) == 0)
                {
                    dp[i] = min(dp[i], dp[i + len]);
                }
            }
        }
        return dp[0];
    }
};

這邊我用了 C 的 `memcmp` ，用法可以參考[這裡](https://learn.microsoft.com/zh-tw/cpp/c-runtime-library/reference/memcmp-wmemcmp?view=msvc-170)

這個會比較傳入的兩個緩衝區 `buffer1` 跟 `buffer2` 前 `count` 個字元，如果兩緩衝區相等就會回傳 `0`
所以這邊才寫 `memcmp(s.data() + i, word.data(), len) == 0`

關於 `string::data` 可以參見[這裡](https://cplusplus.com/reference/string/string/data/)
總之它會回傳 C-string 表達的指標


這樣寫，結果挺不錯的

***

然後我後來才知道 C++ 的 string 還有[string::compare](https://cplusplus.com/reference/string/string/compare/)
笑死


(看到別人有用，它寫法基本跟我一樣，只差把 C style 的東東改成 C++的就好)