My 0ms solution using DP


  • 0
    C

    int len1 = s1.length();

    int len2 = s2.length();
    
    if (len1 + len2 != s3.length()) return false;
    
    int **table = new int*[len1+1];
    
    for(int i=0; i<=len1; i++) 
    
    {
    
        table[i] = new int [len2 + 1];
    
        memset(table[i], 0, sizeof(int) * (len2 + 1));
    
    }
    
    table[0][0] = 1;
    
    for (int i=1; i<=len1 && s1[i-1] == s3[i-1]; i++)table[i][0] = 1;
    
    for (int i=1; i<=len2 && s2[i-1] == s3[i-1]; i++)table[0][i] = 1;
    
    for (int i=1; i<=len1; i++)
    
    {
    
        for(int j=1; j<=len2; j++)
    
        {
    
            if (table[i-1][j] && s1[i-1] == s3[i+j-1]) table[i][j] = 1;
    
            else if (table[i][j-1] && s2[j-1] == s3[i+j-1]) table[i][j] = 1;
    
        }
    
    }
    
    return table[len1][len2];

Log in to reply
 

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