顺序遍历 + 双指针，求解《777. 在LR字符串中交换相邻字符》

代码技巧:双指针语言:JavaScript 语言:Go 语言:PHP 语言:Python 语言:C 语言:C++语言:C#语言:TypeScript 语言:Java

2022-10-02 03:22:30

顺序遍历 + 双指针，求解《777. 在LR字符串中交换相邻字符》

例题

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
提示：
1 <= len(start) = len(end) <= 10000。
start和end中的字符串仅限于'L', 'R'和'X'。

答案

顺序遍历 · 双指针

var canTransform = function(start, end) {
  const n = start.length
  let i = j = 0
  while (i < n && j < n) {
    while (i < n && start[i] === 'X') i++;
    while (j < n && end[j] === 'X') j++;
    if (i < n && j < n) {
      if (start[i] !== end[j]) return false
      if (start[i] === 'L' && i < j || start[i] === 'R' && i > j) return false
      i++
      j++
    }
  }
  while (i < n) {
    if (start[i] !== 'X') return false
    i++
  }
  while (j < n) {
    if (end[j] !== 'X') return false
    j++
  }
  return true
};

function canTransform(start: string, end: string): boolean {
  const n = start.length
  let i = 0, j = 0
  while (i < n && j < n) {
    while (i < n && start[i] === 'X') i++
    while (j < n && end[j] === 'X') j++
    if (i < n && j < n) {
      if (start[i] !== end[j]) return false
      if (start[i] === 'L' && i < j || start[i] === 'R' && i > j) return false
      i++
      j++
    }
  }
  while (i < n) {
    if (start[i] !== 'X') return false
    i++
  }
  while (j < n) {
    if (end[j] !== 'X') return false
    j++
  }
  return true
};

class Solution {
  function canTransform($start, $end) {
    $n = strlen($start);
    $i = 0;
    $j = 0;
    while ($i < $n && $j < $n) {
      while ($i < $n && $start[$i] === 'X') $i++;
      while ($j < $n && $end[$j] === 'X') $j++;
      if ($i < $n && $j < $n) {
        if ($start[$i] !== $end[$j]) return false;
        if ($start[$i] === 'L' && $i < $j || $start[$i] === 'R' && $i > $j) return false;
        $i++;
        $j++;
      } 
    }
    while ($i < $n) {
      if ($start[$i] !== 'X') return false;
      $i++;
    }
    while ($j < $n) {
      if ($end[$j] !== 'X') return false;
      $j++;
    }
    return true;
  }
}

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

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) {
        if (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++;
      }
    }
    while (i < n) {
      if (start.charAt(i) != 'X') return false;
      i++;
    }
    while (j < n) {
      if (end.charAt(j) != 'X') return false;
      j++;
    }
    return true;
  }
}

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

bool canTransform(char * start, char * end){
  int n = strlen(start), i = 0, j = 0;
  while (i < n && j < n) {
    while (i < n && start[i] == 'X') i++;
    while (j < n && end[j] == 'X') j++;
    if (i < n && j < n) {
      if (start[i] != end[j]) return false;
      if (start[i] == 'L' && i < j || start[i] == 'R' && i > j) return false;
      i++;
      j++;
    }
  }
  while (i < n) {
    if (start[i] != 'X') return false;
    i++;
  }
  while (j < n) {
    if (end[j] != 'X') return false;
    j++;
  }
  return true;
}

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

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

小宇

Github　力扣　 M站　全部原创，请勿转载