Can anyone help on why my c++ code is so slow? (1627 ms)


  • 0

    Hi, can anyone take a look on why is my cpp code below so slow? it got accepted but took 1627 ms.
    I found a similar Java version which only took 80 ms: https://discuss.leetcode.com/topic/22516/my-java-dp-solution-using-2d-table/6

    Thanks!

        /*
            dp[i][j] := whether s[0..i-1] matchs p[0..j-1], i = [0 : s.size()], j = [0, p.size()]
            1. if (s[i-1] == p[j-1] || p[j-1] == '?') -> dp[i][j] = dp[i-1][j-1]
            2. else if (p[j-1] == '*') -> dp[i][j] = dp[i-1][j] || dp[i][j-1]
            3. else (i.e. s[i] != p[j-1]) -> dp[i][j] = false 
        */
        bool isMatch(string s, string p) {
            int m = s.size();
            int n = p.size();
            
            vector<vector<bool> > dp(m + 1, vector<bool>(n + 1)); // default to all false
            
            // initialize first column and row
            dp[0][0] = true; // s and p are both ""
            for (int j = 1; j <= n; ++ j) {
                if (p[j-1] == '*')
                    dp[0][j] = true;
                else
                    break; // if current is not '*', will not match onwards
            }
            
            for (int i = 1; i <= m; ++ i) {
                for (int j = 1; j <= n; ++ j) {
                    if (s[i-1] == p[j-1] || p[j-1] == '?') // if current char match
                        dp[i][j] = dp[i-1][j-1];
                    else if (p[j-1] == '*')
                        dp[i][j] = dp[i-1][j] || dp[i][j-1];
                    // else, no match, leave as false
                }
            }
            
            return dp[m][n];
        }
    

  • 0

    @ivan2 Using array instead of vector is the key. Besides there is no need to use two dimensional array, check this.

    class Solution {
    public:
        bool isMatch(string s, string p) 
        {
            int sLen = s.length(), pLen = p.length();
            vector<bool> match(sLen+1, false);
            match[0] = true;
            for(int i = 1; i <= pLen; ++i)
            {
                if(p[i-1] == '*')
                    for(int j = 1; j <= sLen; ++j)
                        match[j] = match[j] || match[j-1];
                else
                {
                    for(int j = sLen; j > 0; --j)
                        match[j] = match[j-1] && (p[i-1]=='?' || p[i-1]==s[j-1]);
                    match[0] = false;
                }
            }
            return match[sLen];
        }
    };
    

  • 0

    Thanks @LHearen

    However I got "Runtime_Error" when using an array instead of a vector, for large inputs (> 4000), I guess it's Leetcode OJ's stack being too small...


  • 0

    @ivan2 Leetcode has been further optimised to ensure the robustness of the test cases, so it's quite normal. Besides in this case it's also a good sign for you to reduce your space complexity to one dimension.


  • 0

    @LHearen That's very fair, thanks a lot for the help!


Log in to reply
 

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