• 困难
  • 中等
  • 简单

    题目描述

    给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。

    来源，leetcode 每日一题 87. 扰乱字符串

image.png
image.png

解题思路

image.png
image.png

代码

  1. class Solution {
  2. public:
  3.     bool isScramble(string s1, string s2) {
  4.         int length = s1.length();
  5.         if (length != s2.length()) {
  6.             return false;
  7.         }
  8.         vector<vector<vector<bool>>> dp(length, vector<vector<bool>>(length, vector<bool>(length+1, false)));
  9.         for (int i = 0; i < length; i++) {
  10.             for (int j = 0; j < length; j++){
  11.                 dp[i][j][1] = (s1[i] == s2[j]);
  12.             }
  13.         }
  14.         for (int sublen = 2; sublen <= length; sublen++) {
  15.             for (int i = 0; i <= length - sublen; i++) {
  16.                 for (int j = 0; j <= length - sublen; j++) {
  17.                     for (int k = 1; k < sublen; k++) {
  18.                         // 第一种情况：S1 -> T1, S2 -> T2
  19.                         if (dp[i][j][k] && dp[i + k][j + k][sublen - k]) {
  20.                             dp[i][j][sublen] = true;
  21.                             break;
  22.                         }
  23.                         // 第二种情况：S1 -> T2, S2 -> T1
  24.                         // S1 起点 i，T2 起点 j + 前面那段长度 len-k ，S2 起点 i + 前面长度k
  25.                         if (dp[i][j + sublen - k][k] && dp[i + k][j][sublen - k]) {
  26.                             dp[i][j][sublen] = true;
  27.                             break;
  28.                         }
  29.                     }
  30.                 }
  31.             }
  32.         }
  33.         return dp[0][0][length];
  34.     }
  35. };