0777. Swap Adjacent in LR String¶
题目信息¶
- 题号:
0777
- 难度:
Medium
- 主题:
字符串、受限移动、可达性
- 原题:
- 重点:
只允许把
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"。