Solved with DP but got a wired problem


  • 0
    W

    Below is my solution using DP and it passed the OJ.
    But if I change the condition of for loops from i + 1 <= s.size() to i < s.size(), I will never go into the for loop, skip the loop (same for j) and get wrong answers.
    If I changed from i + 1 <= s.size() to i < size1, where size1 is assigned with s.size(), the solution can also passed OJ.
    It is wired. Since I think these three conditions are equivalent.
    Could anyone explain it? Thanks!

    bool isMatch(string s, string p) {
            bool M[s.size() + 1][p.size() + 1];
            
            for (int i = -1; i + 1 <= s.size(); i++) {
                for (int j = -1; j + 1 <= p.size(); j++) {
                    if (i == -1 && j == -1)
                        M[i + 1][j + 1] = true;
                    else if (i == -1)
                        M[i + 1][j + 1] = (M[i + 1][j] && p[j] == '*');
                    else if (j == -1)
                        M[i + 1][j + 1] = false;
                    else {
                        if (p[j] != '*')
                            M[i + 1][j + 1] = M[i][j] && (p[j] == '?' || s[i] == p[j]);
                        else
                            M[i + 1][j + 1] = (M[i + 1][j] || M[i][j + 1]);
                    }
                }
            }
            return M[s.size()][p.size()];
        }
    

Log in to reply
 

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