0777. Swap Adjacent in LR String

题目信息

题号:

0777

难度:

Medium

主题:

字符串、受限移动、可达性

原题:

LeetCode 0777

重点:

只允许把 XL 替换为 LX,或把 RX 替换为 XR;因此 L 只能向左移动、R 只能向右移动,且非 X 字符的相对次序不能改变

题目重述

给定长度相同的字符串 start 和 end,两者只包含字符 L、R 和 X。字符 X 表示空位。

一次操作可以选择一个相邻子串并执行以下一种替换:把 "XL" 变为 "LX",即让 L 向左移动一格;或把 "RX" 变为 "XR",即让 R 向右移动一格。不能执行相反方向的替换。

请判断是否可以经过零次或多次操作,把 start 变为 end。1 <= start.length == end.length <= 10^4。

自建示例

两种合法移动先后发生:

输入:start = "RXXL", end = "XRLX"
输出:true
解释:先把开头的 "RX" 变为 "XR",得到 "XRXL";再把末尾的 "XL" 变为 "LX",得到 "XRLX"。

L 不能向右移动:

输入:start = "LX", end = "XL"
输出:false
解释:允许的替换只能让 L 从 "XL" 中向左移动,不能把 "LX" 变为 "XL"。