Skip to content

Latest commit

 

History

History
188 lines (151 loc) · 5.14 KB

README.md

File metadata and controls

188 lines (151 loc) · 5.14 KB
Raw
comments difficulty edit_url tags
true
中等
双指针
字符串

777. 在 LR 字符串中交换相邻字符

English Version

题目描述

在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个 "LX" 替换一个 "XL"，或者用一个 "XR" 替换一个 "RX"。现给定起始字符串 start 和结束字符串 end，请编写代码，当且仅当存在一系列移动操作使得 start 可以转换成 end 时， 返回 True。

 

示例 1：

输入：start = "RXXLRXRXL", end = "XRLXXRRLX"
输出：true
解释：通过以下步骤我们可以将 start 转化为 end：
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

示例 2：

输入：start = "X", end = "L"
输出：false

 

提示：

  • 1 <= start.length <= 104
  • start.length == end.length
  • start 和 end 都只包含 'L', 'R' 或 'X'。

解法

方法一：双指针

替换操作实际上是将 L 往左移动（L 左边为 X 时才能移动），R 往右移动（R 右边是 X 时才能移动），但 L 无法穿过 R。所以，如果去掉 start 和 end 中的所有 X，剩下的字符应该是相同的，否则返回 false。

双指针遍历 start 和 end：

  • 如果当前字符为 L 且 $i\lt j$，那么这个 L 无法向右移动，返回 false；
  • 如果当前字符为 R 且 $i\gt j$，那么这个 R 无法向左移动，返回 false。

如果双指针均遍历到末尾，返回 true。

时间复杂度 $O(n)$，其中 $n$ 表示字符串 start 或 end 的长度。

相似题目：

Python3

class Solution:
    def canTransform(self, start: str, end: str) -> bool:
        n = len(start)
        i = j = 0
        while 1:
            while i < n and start[i] == 'X':
                i += 1
            while j < n and end[j] == 'X':
                j += 1
            if i >= n and j >= n:
                return True
            if i >= n or j >= n or start[i] != end[j]:
                return False
            if start[i] == 'L' and i < j:
                return False
            if start[i] == 'R' and i > j:
                return False
            i, j = i + 1, j + 1

Java

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

C++

class Solution {
public:
    bool canTransform(string start, string end) {
        int n = start.size();
        int i = 0, j = 0;
        while (true) {
            while (i < n && start[i] == 'X') ++i;
            while (j < n && end[j] == 'X') ++j;
            if (i == n && j == n) return true;
            if (i == n || j == n || start[i] != end[j]) return false;
            if (start[i] == 'L' && i < j) return false;
            if (start[i] == 'R' && i > j) return false;
            ++i;
            ++j;
        }
    }
};

Go

func canTransform(start string, end string) bool {
	n := len(start)
	i, j := 0, 0
	for {
		for i < n && start[i] == 'X' {
			i++
		}
		for j < n && end[j] == 'X' {
			j++
		}
		if i == n && j == n {
			return true
		}
		if i == n || j == n || start[i] != end[j] {
			return false
		}
		if start[i] == 'L' && i < j {
			return false
		}
		if start[i] == 'R' && i > j {
			return false
		}
		i, j = i+1, j+1
	}
}