首页 > 试题广场 >

搅乱字符串

[编程题]搅乱字符串
  • 热度指数:10276 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
题目给出一个字符串s1,我们可以用递归的方法将字符串分成两个非空的子串来将s1表示成一个二叉树
下面是s1=“coder”的一种二叉树的表现形式:
coder
/    \
co   der
/ \    /  \
c   o  d   er
/ \
e   r
将字符串乱序的方法是:选择任意的非叶子节点,交换它的两个孩子节点。
例如:如果我们选择节点“co”交换他的两个孩子节点,就会产生一个乱序字符串"ocder".
    ocder
    /    \
  oc    der
 / \    /  \
o   c  d   er
           / \
          e   r

我们称"ocder"是"coder"的一个乱序字符串。
类似的:如果我们继续交换“der”的两个孩子节点和“at”的两个孩子节点,会产生乱序字符串"ocred"
    ocred
   /    \
  oc    red
 / \    /  \
o   c  re   d
       / \
      r   e
我们称"ocred"是"coder"的一个乱序字符串。
给出两个长度相同的字符串s1 和 s2,请判断s2是否是s1的乱序字符串。
示例1

输入

"ab","ab"

输出

true
示例2

输入

"ba","ab"

输出

true
头像 诗云panther
发表于 2021-08-21 15:12:50
class Solution {public: bool isScramble(string s1, string s2) { if(s1 == s2) return true; int c[26] = {0}; for(int 展开全文
头像 华科不平凡
发表于 2020-08-30 16:17:49
牛客的标签里面有“动态规划”,搞得我一脸懵逼😳 本题应该用递归/贪心实现,条件如下: 基准1: 如果两个字符串长度不相等,返回false 基准2: 如果两个字符串相等,返回false 基准3: 如果两个字符串中对应字符的个数不相等,返回false 递归判断子字符串是否是乱序字符串 代码如下: 展开全文