0087. Scramble String

题目信息

题号:
  1. 扰乱字符串

难度:

Hard

主题:

字符串、记忆化搜索、区间动态规划

原题:

LeetCode 0087

重点:

从递归枚举切分,推导到三维状态缓存与区间动态规划

题目重述

给定两个字符串 s1 和 s2。对一个长度大于 1 的字符串,可以在任意位置把它切成两个非空子串, 然后选择保持左右顺序或交换左右子串,再对两个子串递归执行相同操作。

判断 s2 能否由 s1 经过上述操作得到。两个字符串只包含小写英文字母,长度均不超过 30。

自建示例

输入:s1 = "abc", s2 = "bca"
输出:true

把 abc 切为 a | bc,交换两个部分后得到 bc | a,即 bca。

输入:s1 = "abcd", s2 = "bdac"
输出:false

两个字符串字符频次相同,但不存在一棵递归切分树,使每个节点都能通过保持或交换两个孩子完成对应。

输入:s1 = "great", s2 = "rgeat"
输出:true

可以把 great 切为 gr | eat。左侧 gr 交换为 rg,右侧 eat 保持不变。

C++ 实现

#include <array>
#include <string>
#include <vector>

class Solution {
private:
    std::string first;
    std::string second;
    std::vector<std::array<int, 26>> first_prefix;
    std::vector<std::array<int, 26>> second_prefix;
    std::vector<std::vector<std::vector<int>>> memo;

    void buildPrefixCounts() {
        int n = static_cast<int>(first.size());
        first_prefix.assign(n + 1, {});
        second_prefix.assign(n + 1, {});

        for (int index = 0; index < n; ++index) {
            first_prefix[index + 1] = first_prefix[index];
            second_prefix[index + 1] = second_prefix[index];
            ++first_prefix[index + 1][first[index] - 'a'];
            ++second_prefix[index + 1][second[index] - 'a'];
        }
    }

    bool sameCharacters(int first_start, int second_start, int length) const {
        for (int letter = 0; letter < 26; ++letter) {
            int first_count = first_prefix[first_start + length][letter] -
                              first_prefix[first_start][letter];
            int second_count = second_prefix[second_start + length][letter] -
                               second_prefix[second_start][letter];
            if (first_count != second_count) {
                return false;
            }
        }
        return true;
    }

    bool equalRange(int first_start, int second_start, int length) const {
        for (int offset = 0; offset < length; ++offset) {
            if (first[first_start + offset] != second[second_start + offset]) {
                return false;
            }
        }
        return true;
    }

    bool plainRecursion(int first_start, int second_start, int length) {
        if (equalRange(first_start, second_start, length)) {
            return true;
        }
        if (!sameCharacters(first_start, second_start, length)) {
            return false;
        }

        for (int split = 1; split < length; ++split) {
            bool keep_order =
                plainRecursion(first_start, second_start, split) &&
                plainRecursion(first_start + split,
                               second_start + split,
                               length - split);

            bool swap_order =
                plainRecursion(first_start,
                               second_start + length - split,
                               split) &&
                plainRecursion(first_start + split,
                               second_start,
                               length - split);

            if (keep_order || swap_order) {
                return true;
            }
        }
        return false;
    }

    bool memoizedRecursion(int first_start, int second_start, int length) {
        int& cached = memo[first_start][second_start][length];
        if (cached != -1) {
            return cached == 1;
        }

        if (equalRange(first_start, second_start, length)) {
            cached = 1;
            return true;
        }
        if (!sameCharacters(first_start, second_start, length)) {
            cached = 0;
            return false;
        }

        for (int split = 1; split < length; ++split) {
            bool keep_order =
                memoizedRecursion(first_start, second_start, split) &&
                memoizedRecursion(first_start + split,
                                  second_start + split,
                                  length - split);

            bool swap_order =
                memoizedRecursion(first_start,
                                  second_start + length - split,
                                  split) &&
                memoizedRecursion(first_start + split,
                                  second_start,
                                  length - split);

            if (keep_order || swap_order) {
                cached = 1;
                return true;
            }
        }

        cached = 0;
        return false;
    }

    bool intervalDp(const std::string& s1, const std::string& s2) {
        int n = static_cast<int>(s1.size());
        std::vector<std::vector<std::vector<char>>> dp(
            n,
            std::vector<std::vector<char>>(
                n,
                std::vector<char>(n + 1, false)));

        for (int first_start = 0; first_start < n; ++first_start) {
            for (int second_start = 0; second_start < n; ++second_start) {
                dp[first_start][second_start][1] =
                    s1[first_start] == s2[second_start];
            }
        }

        for (int length = 2; length <= n; ++length) {
            for (int first_start = 0; first_start + length <= n; ++first_start) {
                for (int second_start = 0;
                     second_start + length <= n;
                     ++second_start) {
                    for (int split = 1; split < length; ++split) {
                        bool keep_order =
                            dp[first_start][second_start][split] &&
                            dp[first_start + split]
                              [second_start + split]
                              [length - split];

                        bool swap_order =
                            dp[first_start]
                              [second_start + length - split]
                              [split] &&
                            dp[first_start + split]
                              [second_start]
                              [length - split];

                        if (keep_order || swap_order) {
                            dp[first_start][second_start][length] = true;
                            break;
                        }
                    }
                }
            }
        }

        return dp[0][0][n];
    }

public:
    bool isScramble(std::string s1, std::string s2) {
        if (s1.size() != s2.size()) {
            return false;
        }

        first = s1;
        second = s2;
        int n = static_cast<int>(first.size());

        buildPrefixCounts();
        memo.assign(
            n,
            std::vector<std::vector<int>>(
                n,
                std::vector<int>(n + 1, -1)));

        return memoizedRecursion(0, 0, n);
    }
};

题解

递归切分

一个扰乱过程可以看成一棵二叉树。树中每个节点保存一段字符串,并在某个位置切成左右两个非空部分。 根节点对子节点只有两种安排:保持左右顺序,或交换左右顺序。

令状态 solve(i, j, length) 表示:

s1[i : i + length]

能否扰乱成:

s2[j : j + length]

在 split 处分割第一个区间后,保持顺序时需要同时满足:

solve(i,         j,         split)
solve(i + split, j + split, length - split)

交换顺序时,第一个区间左侧应对应第二个区间末尾同样长的部分:

solve(i,         j + length - split, split)
solve(i + split, j,                  length - split)

只要某个切分点的一种安排中两个子状态都成立,当前状态就成立。

必要条件剪枝

扰乱操作只改变子串位置,不会改变字符多重集。两个对应区间的字符频次不同,当前状态必定失败。

逐状态重新扫描区间会产生额外重复。前缀频次数组保存每个字符在任意前缀中的出现次数,区间频次可由两次前缀相减得到, 每次剪枝只需比较 26 个字符。

两个区间内容完全相同时,可以直接返回成功,不必继续枚举切分点。剪枝顺序因此是:

区间完全相等 -> 成功
字符频次不同 -> 失败
其余情况     -> 枚举切分点

重复状态

不同的上层切分可能到达相同的 (i, j, length)。朴素递归会反复求解这些区间,搜索树随长度快速膨胀。

三维缓存为每个状态保存未知、失败、成功三种结果。失败状态同样必须缓存,否则大量无法匹配的区间仍会被重复搜索。

区间动态规划

记忆化搜索按需要访问状态。自底向上的写法使用同一个三维定义:

dp[i][j][length]

长度为 1 时,只需比较两个字符。长度大于 1 的状态只依赖两个更短区间,因此按 length 从小到大填表即可。

两种写法拥有相同的状态和转移。记忆化搜索能利用频次剪枝跳过大量不可达状态,通常更直接;区间 DP 没有递归调用,遍历顺序更固定。

正确性

任意合法扰乱树的根节点必有一个切分点,并且根节点只可能保持或交换两个孩子。算法枚举全部切分点和这两种安排, 因此合法扰乱不会遗漏。

反过来,算法只有在某个切分点的两个子状态都成立时才返回成功。把两个子状态对应的合法扰乱树连接到当前根节点, 即可构造当前区间的合法扰乱树,因此不会产生错误的成功结果。

复杂度

状态数为 O(n^3),每个状态最多枚举 O(n) 个切分点,记忆化搜索和区间 DP 的时间上界均为 O(n^4)。 前缀频次剪枝每次比较固定 26 个字符,不改变渐进复杂度。

三维缓存或 DP 表使用 O(n^3) 空间;记忆化搜索的递归深度为 O(n)。朴素递归没有缓存,最坏呈指数增长。