Leetcode 51-100

• 87. 扰乱字符串
• 92. 反转链表 II

87. 扰乱字符串

位压缩的记忆化搜索。

class Solution {
    unordered_map<int, bool> res;

public:
    bool dfs(const string& s1, const string& s2, int x1, int x2, int n) {
        if (n == 1) return s1[x1] == s2[x2];
        int index = (x1 << 10) | (x2 << 5) | n;
        if (res.find(index) != res.end()) return res[index];
        for (int i = 1; i < n; ++i) {
            if (dfs(s1, s2, x1, x2, i) && dfs(s1, s2, x1 + i, x2 + i, n - i)) {
                res[index] = true;
                return true;
            }
            if (dfs(s1, s2, x1, x2 + n - i, i) &&
                dfs(s1, s2, x1 + i, x2, n - i)) {
                res[index] = true;
                return true;
            }
        }
        res[index] = false;
        return false;
    }
    bool isScramble(string s1, string s2) {
        res.clear();
        return dfs(s1, s2, 0, 0, (int)s1.size());
    }
};

92. 反转链表 II

@medium 逐个反转链表节点。