Question

How to find whether a string s3 is formed by an interleaving of the strings s1 and s2 in C++

Answer 1

#include <iostream>
#include <vector>

bool isInterleave(std::string s1, std::string s2, std::string s3) {
    int s1size = s1.size(), s2size = s2.size();
    
    if (s1size + s2size != s3.size()) return false;

    std::vector<std::vector<bool>> vec(s1size + 1, std::vector<bool>(s2size + 1, false));
    vec[0][0] = true;

    for (int i = 0; i <= s1size; i++) {
        for (int j = 0; j <= s2size; j++) {
            if (i > 0 && s1[i - 1] == s3[i + j - 1])
                vec[i][j] = vec[i][j] || vec[i - 1][j];
            if (j > 0 && s2[j - 1] == s3[i + j - 1])
                vec[i][j] = vec[i][j] || vec[i][j - 1];
        }
    }

    return vec[s1size][s2size];
}

int main() {
    std::string s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";
    
    std::cout << (isInterleave(s1, s2, s3) ? "true" : "false");
    
}



/*
run:

true

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>

bool isInterleave(std::string s1, std::string s2, std::string s3) {
    int s1size = s1.length(), s2size = s2.length();
    
    if (s1size + s2size != s3.length()) return false;

    std::vector<bool> vec(s1size + 1, false);
    vec[0] = true;

    for (int j = 1; j <= s1size; j++) {
        vec[j] = vec[j - 1] && (s2[j - 1] == s3[j - 1]);
    }

    for (int i = 1; i <= s2size; i++) {
        vec[0] = vec[0] && (s1[i - 1] == s3[i - 1]);
        for (int j = 1; j <= s1size; j++) {
            vec[j] = (vec[j] && s1[i - 1] == s3[i + j - 1]) ||
                     (vec[j - 1] && s2[j - 1] == s3[i + j - 1]);
        }
    }

    return vec[s1size];
}

int main() {
    std::string s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac";
    
    std::cout << (isInterleave(s1, s2, s3) ? "true" : "false");
}



/*
run:

true

*/

 

70+ SQL courses for beginners and professionals