Description

Submission

class Solution {
    unordered_set<int> visited; // the failed cases

    vector<string> parse(string& s) {
        int n = s.length();
        vector<string> rets;
        for(int i = 0; i < n; ++i) {
            if(isalpha(s[i])) {
                rets.push_back(s.substr(i, 1));
            } else {
                int j = i;
                for(; j < n && isdigit(s[j]); ++j);
                rets.push_back(s.substr(i, j - i));
                i = j - 1;
            }
        }
        return rets;
    }

    unordered_set<int> getNums(string& s) {
        int n = s.length();
        int t = stoi(s);

        if(n == 1) {
            return {t};
        }

        if(n == 2) {
            int a = t % 10;
            int b = t / 10;
            return {a + b, t};
        }

        if(n == 3) {
            int a = t / 100;
            int b = (t / 10) % 10;
            int c = t % 10;

            return {a + b + c, a * 10 + b + c, a + b * 10 + c, t};
        }
        return {};
    }

    // 2 pairs of tokens, pointer, number of universal matchers left
    bool dfs(vector<string>& t1, int p1, int n1, vector<string>& t2, int p2, int n2) {
        if(p1 == t1.size() && p2 == t2.size()) return n1 == n2;

        long long hash = (long long) p1 * 1e10 + n1 * 1e8 + p2 * 1e5 + n2 * 1e3;
        if(visited.find(hash) != visited.end()) return false;
        
        if(p1 == t1.size() && n1 == 0) {
            visited.insert(hash);
            return false;
        }
        if(p2 == t2.size() && n2 == 0) {
            visited.insert(hash);
            return false;
        }

        if(p1 < t1.size() && isdigit(t1[p1][0])) {
            unordered_set<int> nums = getNums(t1[p1]);
            for(int x: nums) {
                if(dfs(t1, p1 + 1, n1 + x, t2, p2, n2)) return true;
            }
            visited.insert(hash);
            return false;
        }

        if(p2 < t2.size() && isdigit(t2[p2][0])) {
            unordered_set<int> nums = getNums(t2[p2]);
            for(int x: nums) {
                if(dfs(t1, p1, n1, t2, p2 + 1, n2 + x)) return true;
            }
            visited.insert(hash);
            return false;
        }

        if(n1 != 0 && n2 != 0) {
            int common = min(n1, n2);
            return dfs(t1, p1, n1 - common, t2, p2, n2 - common);
        } 

        if(n1 != 0 && n2 == 0) {
            return dfs(t1, p1, n1 - 1, t2, p2 + 1, 0);
        }

        if(n1 == 0 && n2 != 0) {
            return dfs(t1, p1 + 1, 0, t2, p2, n2 - 1);
        }

        if(n1 == 0 && n2 == 0) {
            if(t1[p1] != t2[p2]) {
                visited.insert(hash);
                return false;
            }
            return dfs(t1, p1 + 1, 0, t2, p2 + 1, 0);
        }

        visited.insert(hash);
        return false;
    }

public:
    bool possiblyEquals(string s1, string s2) {
        vector<string> t1 = parse(s1);
        vector<string> t2 = parse(s2);
        return dfs(t1, 0, 0, t2, 0, 0);
    }
};

// "internationalization" => i n t e r 
// "i18n"                    i 18 n