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

题目描述：在一个由 '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

题解

官方法一

• 转换不变性：字符串中的 'L' 和 'R' 是不会互相穿插的，意味着开始和结束的字符串如果只看 'L' 和 'R' 的话是一模一样的。

• 可到达性：设 $(i_1, i_2, \cdots )，(i^{‘}_1, i^{‘}_2, \cdots )$为每个字符 ‘L’ 在原始字符串和目标字符串的位置，$(j_1, j_2, \cdots )(j^{‘}_1, j^{‘}_2, \cdots )$为每个字符 ‘R’ 在原始字符串和目标字符串的位置，如果$i_k \geq i^{‘}_k $和 $j_k \leq j^{‘}_k $都能满足，这个字符串就是 ”可到达的“。

  L只能向左移，R只能向右移

class Solution(object):
    def canTransform(start, end):
        if start.replace('X','') != end.replace('X', ''):
            return False

        for (symbol, op) in (('L', operator.ge), ('R', operator.le)):
          # ge() >=  ; le() <= 
            B = (i for i, c in enumerate(end) if c == symbol)
            for i, c in enumerate(start):
                if c == symbol and not op(i, next(B)):
                    return False

        return True

• enumerate() 函数

  enumerate(sequence, [start=0])
  
      sequence -- 一个序列、迭代器或其他支持迭代对象。
      start -- 下标起始位置。
      返回 enumerate(枚举) 对象

  >>>seq = ['one', 'two', 'three']
  >>> for i, element in enumerate(seq):
  ...     	print( i, element)
  ... 
  0 one
  1 two
  2 three

官方解二：双指针

class Solution(object):
    def canTransform(self, start, end):
        # For (i, x) and (j, y) in enumerate(start), enumerate(end)
        # where x != 'X' and y != 'X',
        # and where if one exhausts early, it's elements are (None, None),...
        for (i, x), (j, y) in itertools.zip_longest(
                ((i, x) for i, x in enumerate(start) if x != 'X'),
                ((j, y) for j, y in enumerate(end) if y != 'X'),
                fillvalue = (None, None)):

            # If not solid or accessible, return False
            if x != y or (x == 'L' and i < j) or (x == 'R' and i > j):
                return False

        return True

• zip()、zip.longest()

  a = [1,2,3,4]
  b = [5,6,7]
  print(list(zip(a,b))) # 两个可迭代参数长度不同时，按最短的组合输出
  # 输出：[(1, 5), (2, 6), (3, 7)]
  
  print(list(zip_longest(a,b)))#按最长的输出，长度不足的用None进行代替
  # 输出：[(1, 5), (2, 6), (3, 7), (4, None)]

用时最快

class Solution:
    def canTransform(self,star,end):
        if start.replace('X','')!= end.replace('x',''):
            return False
        sl,el,sr,er = 0,0,0,0
        for i in range(len(start)):
            if start[i]=='L':
                sl+=1
            if start[i]=='R':
                sr+=1
            if end[i]=='L':
                el+=1
            if end[i]=='R':
                er+=1
            if sl>el or sr<er:
                return False
                
        return True