Problem 31: Interleaving Strings

Problem Statement: Given three strings a, b, and c, determine if c is formed by interleaving the characters of a and b in a way that maintains the left-to-right ordering of the characters from a and from b.

Input

The first line contains string a, the second line contains string b and the third line contains string c.

Output

Print "YES" if c is a valid interleaving of a and b, otherwise print "NO".

Examples


Input:
abc
def
adbcef

Output:
YES

Solution in C++


#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a, b, c;
    cin >> a >> b >> c;
    int n = a.size(), m = b.size();
    if(c.size() != n + m){
        cout << "NO\n";
        return 0;
    }
    vector<vector<bool>> dp(n+1, vector<bool>(m+1, false));
    dp[0][0] = true;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= m; j++){
            if(i + j == 0) continue;
            if(i > 0 && a[i-1] == c[i+j-1]) dp[i][j] = dp[i][j] || dp[i-1][j];
            if(j > 0 && b[j-1] == c[i+j-1]) dp[i][j] = dp[i][j] || dp[i][j-1];
        }
    }
    cout << (dp[n][m] ? "YES" : "NO") << "\n";
    return 0;
}