2060. Check if an Original String Exists Given Two Encoded Strings

An original string, consisting of lowercase English letters, can be encoded by the following steps:

• Arbitrarily split it into a sequence of some number of non-empty substrings.
• Arbitrarily choose some elements (possibly none) of the sequence, and replace each with its length (as a numeric string).
• Concatenate the sequence as the encoded string.

For example, one way to encode an original string “abcdefghijklmnop” might be:

• Split it as a sequence: [“ab”, “cdefghijklmn”, “o”, “p”].
• Choose the second and third elements to be replaced by their lengths, respectively. The sequence becomes [“ab”, “12”, “1”, “p”].
• Concatenate the elements of the sequence to get the encoded string: “ab121p”.

Given two encoded strings s1 and s2, consisting of lowercase English letters and digits 1-9 (inclusive), return true if there exists an original string that could be encoded as both s1 and s2. Otherwise, return false.

Note: The test cases are generated such that the number of consecutive digits in s1 and s2 does not exceed 3.

class Solution {
    int dp[41][41][2000];
    bool helper(string& o, string& t, int i, int j, int gap) {
        if(i >= o.length() and j >= t.length()) return gap == 0;
        int &res = dp[i][j][gap + 1000];
        if(res != -1) return res;
        res = 0;
        bool od = isdigit(o[i]), td = isdigit(t[j]);
        
        if(i < o.length()) {
            if(isdigit(o[i])) {    
                for(int I = i, jump = 0; I < o.length() and isdigit(o[I]) and !res and I < i + 3; I++) {
                    jump = jump * 10 + (o[I] & 0b1111);
                    res |= helper(o,t,I+1,j,gap + jump);
                }
            } else {
                if(gap < 0) res = helper(o,t,i+1,j,gap + 1);
                else if(!gap and j < t.length() and o[i] == t[j]) res = helper(o,t,i+1,j+1,gap);
            }
        }
            
        if(j < t.length()) {
            if(isdigit(t[j])) {
                for(int J = j, jump = 0; J < t.length() and isdigit(t[J]) and !res and J < j + 3; J++) {
                    jump = jump * 10 + (t[J] & 0b1111);
                    res |= helper(o,t,i,J+1,gap - jump);
                }
            } else if(!res) {
                if(gap > 0) res = helper(o,t,i,j+1,gap - 1);
            }
        }
        
        return res;
    }
public:
    bool possiblyEquals(string s1, string s2) {
       memset(dp,-1,sizeof(dp));
        return helper(s1,s2,0,0,0);
    }
};