My simple 3ms c++ dp solution using one dimension array


  • 1

    dp[i+1] represents how many substring t[0,i] found.
    Fill dp[0] to 1 to avoid conditional statement.
    maxIndex represents the longest substring length we currently found.

        int numDistinct(string s, string t)
        {
            vector<int> dp(t.size() + 1, 0);
            dp[0] = 1;
            int maxIndex = 0;
            for (char c : s)
            {
                for (int i = maxIndex; i >= 0; i--)
                {
                    if (c == t[i])
                    {
                        dp[i + 1] += dp[i];
                        maxIndex = max(maxIndex, i + 1);
                    }
                }
            }
            return dp.back();
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.