0097. Interleaving String ========================= 题目信息 -------- :题号: 0097. 交错字符串 :难度: Medium :主题: 字符串、记忆化搜索、二维动态规划、滚动数组 :原题: `LeetCode 0097 `_ :重点: 从两个来源的递归选择,推导到以较短字符串为列的一维前缀状态 题目重述 -------- 给定字符串 ``s1``、``s2`` 和 ``s3``,判断 ``s3`` 能否由 ``s1`` 与 ``s2`` 交错形成。 构造过程中必须满足: * ``s1`` 中的字符全部使用一次,且相对顺序不变; * ``s2`` 中的字符全部使用一次,且相对顺序不变; * 每次从某个字符串的当前未使用字符中取一个,可以连续多次从同一字符串取字符; * 最终得到的字符串必须恰好等于 ``s3``。 约束为 ``0 <= s1.length, s2.length <= 100``、``0 <= s3.length <= 200``,字符串只包含小写英文字母。 自建示例 -------- .. code-block:: text 输入:s1 = "ab", s2 = "cd", s3 = "acbd" 输出:true 可以依次取 ``a(s1), c(s2), b(s1), d(s2)``,两个来源内部的顺序都没有改变。 .. code-block:: text 输入:s1 = "ab", s2 = "cd", s3 = "adcb" 输出:false 目标中的 ``d`` 出现在 ``c`` 前面,但它们都来自 ``s2``,无法保持 ``s2`` 的原顺序。 .. code-block:: text 输入:s1 = "", s2 = "xyz", s3 = "xyz" 输出:true 一个来源为空时,另一个来源必须与目标完全相同。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: bool plainDfs(const std::string& first, const std::string& second, const std::string& target, int i, int j) { if (i == static_cast(first.size()) && j == static_cast(second.size())) { return true; } int targetIndex = i + j; bool takeFirst = i < static_cast(first.size()) && first[i] == target[targetIndex] && plainDfs(first, second, target, i + 1, j); bool takeSecond = j < static_cast(second.size()) && second[j] == target[targetIndex] && plainDfs(first, second, target, i, j + 1); return takeFirst || takeSecond; } bool memoDfs(const std::string& first, const std::string& second, const std::string& target, int i, int j, std::vector>& memo) { if (i == static_cast(first.size()) && j == static_cast(second.size())) { return true; } int& cached = memo[i][j]; if (cached != -1) return cached == 1; int targetIndex = i + j; bool possible = false; if (i < static_cast(first.size()) && first[i] == target[targetIndex]) { possible = memoDfs(first, second, target, i + 1, j, memo); } if (!possible && j < static_cast(second.size()) && second[j] == target[targetIndex]) { possible = memoDfs(first, second, target, i, j + 1, memo); } cached = possible ? 1 : 0; return possible; } bool memoizedSearch(const std::string& first, const std::string& second, const std::string& target) { std::vector> memo( first.size() + 1, std::vector(second.size() + 1, -1)); return memoDfs(first, second, target, 0, 0, memo); } bool twoDimensionalDp(const std::string& first, const std::string& second, const std::string& target) { int m = static_cast(first.size()); int n = static_cast(second.size()); std::vector> dp( m + 1, std::vector(n + 1, false)); dp[0][0] = true; for (int i = 0; i <= m; ++i) { for (int j = 0; j <= n; ++j) { if (i == 0 && j == 0) continue; int targetIndex = i + j - 1; bool fromFirst = i > 0 && dp[i - 1][j] && first[i - 1] == target[targetIndex]; bool fromSecond = j > 0 && dp[i][j - 1] && second[j - 1] == target[targetIndex]; dp[i][j] = fromFirst || fromSecond; } } return dp[m][n]; } bool oneDimensionalDp(const std::string& first, const std::string& second, const std::string& target) { const std::string* rows = &first; const std::string* columns = &second; if (columns->size() > rows->size()) { const std::string* temporary = rows; rows = columns; columns = temporary; } int rowCount = static_cast(rows->size()); int columnCount = static_cast(columns->size()); std::vector dp(columnCount + 1, false); dp[0] = true; for (int j = 1; j <= columnCount; ++j) { dp[j] = dp[j - 1] && (*columns)[j - 1] == target[j - 1]; } for (int i = 1; i <= rowCount; ++i) { dp[0] = dp[0] && (*rows)[i - 1] == target[i - 1]; for (int j = 1; j <= columnCount; ++j) { int targetIndex = i + j - 1; bool fromRows = dp[j] && (*rows)[i - 1] == target[targetIndex]; bool fromColumns = dp[j - 1] && (*columns)[j - 1] == target[targetIndex]; dp[j] = fromRows || fromColumns; } } return dp[columnCount]; } public: bool isInterleave(std::string s1, std::string s2, std::string s3) { if (s1.size() + s2.size() != s3.size()) return false; return oneDimensionalDp(s1, s2, s3); } }; 题解 ---- 长度守恒 ~~~~~~~~ 交错过程不会删除或复制字符,所以目标长度必须满足: .. code-block:: text len(s3) = len(s1) + len(s2) 该条件不满足时可以立即返回 ``false``,也避免后续递归读取越界的目标下标。 递归选择 ~~~~~~~~ 设已经使用 ``s1`` 的前 ``i`` 个字符和 ``s2`` 的前 ``j`` 个字符。已生成目标前缀的长度必为 ``i+j``,所以下一个目标字符是 ``s3[i+j]``。 当前只有两种合法动作: .. code-block:: text s1[i] == s3[i+j] 时,从 s1 取一个字符,进入 (i+1, j) s2[j] == s3[i+j] 时,从 s2 取一个字符,进入 (i, j+1) 任一分支最终同时耗尽两个来源,就找到一种合法交错。两个当前字符都匹配时必须保留两条分支,不能贪心固定选择某一侧。 重复状态 ~~~~~~~~ 不同的取字符顺序可能到达相同的 ``(i,j)``。到达后,两个来源剩余后缀和目标剩余后缀完全相同,后续答案也相同。 裸递归会重复求解这些状态,最坏呈指数增长。 记忆化数组为每个 ``(i,j)`` 保存未知、失败、成功三种结果,使每个状态至多展开一次。状态数为 ``(m+1)(n+1)``。 前缀动态规划 ~~~~~~~~~~~~ 把递归状态反向解释,定义: .. code-block:: text dp[i][j] = s1 的前 i 个字符与 s2 的前 j 个字符 能否组成 s3 的前 i+j 个字符 最后一个目标字符只可能来自两个位置之一: .. code-block:: text 从 s1 到达:dp[i-1][j] 且 s1[i-1] == s3[i+j-1] 从 s2 到达:dp[i][j-1] 且 s2[j-1] == s3[i+j-1] 两个条件取逻辑或。``dp[0][0]=true`` 表示两个空前缀可以组成空目标;第一行只能连续使用 ``s2``,第一列只能连续使用 ``s1``。 一维压缩 ~~~~~~~~ 二维状态的当前格只依赖上方和左侧: * 更新前的 ``dp[j]`` 保存上一行的 ``dp[i-1][j]``; * 从左向右更新后,``dp[j-1]`` 已保存当前行的 ``dp[i][j-1]``。 因此可以把表压缩成一行。遍历方向必须从左向右;若从右向左,``dp[j-1]`` 仍是上一行状态,便不再代表当前格的左侧来源。 令较短字符串作为列,可以把额外空间降到 ``O(min(m,n))``。交换两个来源不会改变问题,因为只要求分别保持各自内部顺序。 完整性 ~~~~~~ 从 ``dp[0][0]`` 出发,每次转移只追加一个与目标当前位置相同的来源字符,所以所有可达状态都对应合法交错前缀。 反过来,任意合法交错前缀的最后一个字符必来自 ``s1`` 或 ``s2``。删除这个字符后,必落到上方或左侧的前驱状态,因此转移不会遗漏任何方案。最终 ``dp[m][n]`` 恰好表示两个来源全部使用后是否得到完整目标。 复杂度 ~~~~~~ 裸递归最坏为指数时间。记忆化搜索、二维 DP 和一维 DP 都处理 ``O(mn)`` 个状态,时间 ``O(mn)``。 记忆化与二维 DP 使用 ``O(mn)`` 空间;一维 DP 使用 ``O(min(m,n))`` 额外空间。