首页 > 试题广场 >

搅乱字符串

[编程题]搅乱字符串
  • 热度指数: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

这道题你会答吗?花几分钟告诉大家答案吧!