题目描述：

LeetCode 777. Swap Adjacent in LR String

In a string composed of 'L', 'R', and 'X' characters, like "RXXLRXRXL", a move consists of either replacing one occurrence of "XL" with "LX", or replacing one occurrence of "RX" with "XR". Given the starting string start and the ending string end, return True if and only if there exists a sequence of moves to transform one string to the other.

Example:

Input: start = "RXXLRXRXL", end = "XRLXXRRLX"
Output: True
Explanation:
We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Note:

1. 1 <= len(start) = len(end) <= 10000.
2. Both start and end will only consist of characters in {'L', 'R', 'X'}.

题目大意：

字符串由'L', 'R' 和'X'组成。'XL' 可以转换为'LX'，'RX'可以转换为'XR'

给定字符串start和end，求start是否可以通过上述转换变为end。

解题思路：

从左向右遍历start和end，在遍历过程中，start中的字符R的个数应当不小于end中字符R的个数（保证R没有发生相对左移）

从右向左遍历start和end，在遍历过程中，start中的字符L的个数应当不小于end中字符L的个数（保证L没有发生相对右移）

将start和end中的字符'X'移除，用'R'分割两字符串得到的新字符串应相等。

Python代码：

class Solution(object):
    def canTransform(self, start, end):
        """
        :type start: str
        :type end: str
        :rtype: bool
        """
        N = len(start)
        sR = eR = sL = eL = 0
        for x in range(N):
            if start[x] == 'R': sR += 1
            if end[x] == 'R': eR += 1
            if sR < eR: return False
        if sR != eR: return False

        for x in range(N - 1, -1, -1):
            if start[x] == 'L': sL += 1
            if end[x] == 'L': eL += 1
            if sL < eL: return False
        if sL != eL: return False
        
        start, end = start.replace('X', ''), end.replace('X', '')
        return start.split('R') == end.split('R')

 

本文链接：http://bookshadow.com/weblog/2018/02/04/leetcode-swap-adjacent-in-lr-string/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码