2024/09/26 Leetcode Daily Problem

2707. Extra Characters in a String
難度: 中等

題意

給定一字串s及一字串陣列dictionary。
可以將s分割成任意數量的非交疊子字串；求不在字典dictionary中的字串，字元最少有幾個。

範例1
Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
Output: 1
s可分割成"leet"+"s"+"code"，多餘的"s"共有1個字元，故回傳1。

範例2
Input: s = "sayhelloworld", dictionary = ["hello","world"]
Output: 3
s可分割成"say"+"hello"+"world"，多餘的"say"共有3個字元，故回傳3。

思路

動態規劃問題: 問題可以拆解為子問題，而問題可以由子問題的最佳解組合而成。通常會用到填表法來求。

若s長度為n。
設定長度為n+1的整數陣列dp，dp[i]代表s在索引值i ~ n-1的最佳解。
由索引值n - 1到0求解，方便切割字串去dictionary查找，如果反過來求dp感覺很麻煩~
而dp[i]可以是以下的子問題最優解得到:

1. s[i]不選，則s[i]是一個多餘的字元，子問題的解為s[i + 1] + 1。

範例: Input: s = "leetscode", dictionary = ["leet","code","leetcode"]
當i = 4時，s[i] = 's'，若不選s[4]，則此子問題為s[5] + 1。
又s[5]開頭剛好是"code"，s[5] = 1，s[4] = s[5] + 1。

2. s[i]選，則s[i]是dictionary中某個字串的開頭。故從遍歷所有從i開頭的字串，去檢查是否存在於dictionary中。若存在一個長度為len的字串，則此問題的可能解為s[i + len]。

實作

class Solution
{
public:
    int minExtraChar(string s, vector<string> &dictionary)
    {
        // Build hash map for O(1) search
        unordered_set<string> us(dictionary.begin(), dictionary.end());

        int n = (int)s.length();
        // dp[i] is the best solution for substring s[i : n - 1]
        vector<int> dp(n + 1, 0); // Initialize to 0

        // Build dp from tail
        for (int i = n - 1; i >= 0; i--)
        {
            // One solution: s[i] is a extra character
            int curr_min = dp[i + 1] + 1;
            
            // Other solutions: s[i] is a start of substring
            // Traverse all substring start from index i
            for (int len = 1; (i + len) <= n; len++)
            {
                // Find substring in dictionary
                if (us.find(s.substr(i, len)) != us.end())
                {
                    curr_min = min(curr_min, dp[i + len]);
                }
            }
            
            // Update current solution
            dp[i] = curr_min;
        }

        return dp[0];
    }
};

分析

若s長度為N，dictionary有M個字串。
時間複雜度:O(M + N ^ 2)，建立hash table O(M)，遍歷所有子字串O(N ^ 2)
空間複雜度:O(M + N)，Hash table + dp陣列

結果

Accepted
2028/2028 cases passed (125 ms)
Your runtime beats 56.76 % of cpp submissions
Your memory usage beats 52.7 % of cpp submissions (86.8 MB)

這題的測資也太多了吧~~ 應該是週賽的題目才會有如此誇張多的測資。

總結