# Why runtime error using DP?

• 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!

• 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;
*/``````

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

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