Why runtime error using DP?


  • 0
    S

    My code using DP passed every test case on my own machine, but on OJ system it still got runtime error:

    class Solution
    {
    public:
      bool isInterleave(const string& s1, const string& s2, const string& s3)
      {
        int n1 = s1.length(), n2 = s2.length(), n3 = s3.length();
        if (n1 + n2 != n3) return false;
        vector<vector<bool> > F(n1 + 1, vector<bool>(n2 + 1, false));
        F[0][0] = true;
        for (int c = 1; c <= n3; c++) {
          for (int a = 0; a <= c && a <= n1; a++) {
            int b = c - a;
            F[a][b] = ((a >= 1 && s1[a - 1] == s3[c - 1]) && F[a - 1][b]) ||
                      ((b >= 1 && s2[b - 1] == s3[c - 1]) && F[a][b - 1]);        
          }
        }
        return F[n1][n2];
      }
    };
    

    The last executed input before runtime error occurs was:

    s1 = abbbbbbcabbacaacccababaabcccabcacbcaabbbacccaaaaaababbbacbb
    s2 = ccaacabbacaccacababbbbabbcacccacccccaabaababacbbacabbbbabc
    s3 = cacbabbacbbbabcbaacbbaccacaacaacccabababbbababcccbabcabbaccabcccacccaabbcbcaccccaaaaabaaaaababbbbacbbabacbbacabbbbabc
    

    This input can also get correct answer (i.e. true) on my own machine.

    The code is similar to that in https://oj.leetcode.com/discuss/1553/there-trick-here-are-supposed-convert-recursion-to-for-loop. The difference is that the outer loop is the length of s3 -- in such a way we do not need to consider edge cases in which length of s1 or s2 is 0.

    Can anyone help me on this? Many thanks!


  • 2
    F

    Following case can cause run time error:

    n1 = 2, n2 = 2, n3 = 4;
    c = n3 = 4, a = 1, b = c - a = 4 > n2

    /*
    for (int c = 1; c <= n3; c++) {
      for (int a = 0; a <= c && a <= n1; a++) {
        int b = c - a;
    */

  • 0
    S

    Yeah! -- I didn't check the boundary of b. Now I fixed this problem and got AC :) Thanks!


Log in to reply
 

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