宫水三叶的刷题日记

V1

2022/10/02阅读:26主题:前端之巅同款

777. 在LR字符串中交换相邻字符 : 双指针运用题

题目描述

这是 LeetCode 上的 777. 在LR字符串中交换相邻字符 ,难度为 中等

Tag : 「双指针」

在一个由 'L' ,'R''X' 三个字符组成的字符串(例如 "RXXLRXRXL")中进行移动操作。

一次移动操作指用一个 "LX" 替换一个 "XL",或者用一个 "XR" 替换一个 "RX"

现给定起始字符串 start 和结束字符串 end,请编写代码,当且仅当存在一系列移动操作使得 start 可以转换成 end 时, 返回 True

示例 :

输入: start = "RXXLRXRXL", end = "XRLXXRRLX"

输出: True

解释:
我们可以通过以下几步将start转换成end:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

提示:

  • startend 中的字符串仅限于 'L', 'R''X'

双指针

根据题意,我们每次移动要么是将 XL 变为 LX,要么是将 RX 变为 XR,而该两者操作可分别看做将 L 越过多个 X 向左移动,将 R 越过多个 X 向右移动。

因此在 startend 中序号相同的 LR 必然满足坐标性质:

  1. 序号相同的 L : start 的下标不小于 end 的下标(即 L 不能往右移动)
  2. 序号相同的 R : start 的下标不大于 end 的下标(即 R 不能往左移动)

其中「序号」是指在 LR 字符串中出现的相对顺序。

代码:

class Solution {
    public boolean canTransform(String start, String end) {
        int n = start.length(), i = 0, j = 0;
        while (i < n || j < n) {
            while (i < n && start.charAt(i) == 'X') i++;
            while (j < n && end.charAt(j) == 'X') j++;
            if (i == n || j == n) return i == j;
            if (start.charAt(i) != end.charAt(j)) return false;
            if (start.charAt(i) == 'L' && i < j) return false;
            if (start.charAt(i) == 'R' && i > j) return false;
            i++; j++;
        }
        return i == j;
    }
}
  • 时间复杂度:
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.777 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1