Question

2337. 移动片段得到字符串

English Version

题目描述

给你两个字符串 start 和 target ，长度均为 n 。每个字符串 仅 由字符 'L'、'R' 和 '_' 组成，其中：

• 字符 'L' 和 'R' 表示片段，其中片段 'L' 只有在其左侧直接存在一个 空位 时才能向 左 移动，而片段 'R' 只有在其右侧直接存在一个 空位 时才能向 右 移动。
• 字符 '_' 表示可以被 任意 'L' 或 'R' 片段占据的空位。

如果在移动字符串 start 中的片段任意次之后可以得到字符串 target ，返回 true ；否则，返回 false 。

 

示例 1：

输入：start = "_L__R__R_", target = "L______RR"
输出：true
解释：可以从字符串 start 获得 target ，需要进行下面的移动：
- 将第一个片段向左移动一步，字符串现在变为 "L___R__R_" 。
- 将最后一个片段向右移动一步，字符串现在变为 "L___R___R" 。
- 将第二个片段向右移动三步，字符串现在变为 "L______RR" 。
可以从字符串 start 得到 target ，所以返回 true 。

示例 2：

输入：start = "R_L_", target = "__LR"
输出：false
解释：字符串 start 中的 'R' 片段可以向右移动一步得到 "_RL_" 。
但是，在这一步之后，不存在可以移动的片段，所以无法从字符串 start 得到 target 。

示例 3：

输入：start = "_R", target = "R_"
输出：false
解释：字符串 start 中的片段只能向右移动，所以无法从字符串 start 得到 target 。

 

提示：

• n == start.length == target.length
• 1 <= n <= 105
• start 和 target 由字符 'L'、'R' 和 '_' 组成

解法

方法一：双指针

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

我们使用双指针 $i$ 和 $j$ 从头到尾遍历 start 和 target：

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

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

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

相似题目：

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

class Solution:
  def canChange(self, start: str, target: str) -> bool:
    a = [(v, i) for i, v in enumerate(start) if v != '_']
    b = [(v, i) for i, v in enumerate(target) if v != '_']
    if len(a) != len(b):
      return False
    for (c, i), (d, j) in zip(a, b):
      if c != d:
        return False
      if c == 'L' and i < j:
        return False
      if c == 'R' and i > j:
        return False
    return True

class Solution {
  public boolean canChange(String start, String target) {
    List<int[]> a = f(start);
    List<int[]> b = f(target);
    if (a.size() != b.size()) {
      return false;
    }
    for (int i = 0; i < a.size(); ++i) {
      int[] x = a.get(i);
      int[] y = b.get(i);
      if (x[0] != y[0]) {
        return false;
      }
      if (x[0] == 1 && x[1] < y[1]) {
        return false;
      }
      if (x[0] == 2 && x[1] > y[1]) {
        return false;
      }
    }
    return true;
  }

  private List<int[]> f(String s) {
    List<int[]> res = new ArrayList<>();
    for (int i = 0; i < s.length(); ++i) {
      if (s.charAt(i) == 'L') {
        res.add(new int[] {1, i});
      } else if (s.charAt(i) == 'R') {
        res.add(new int[] {2, i});
      }
    }
    return res;
  }
}

using pii = pair<int, int>;

class Solution {
public:
  bool canChange(string start, string target) {
    auto a = f(start);
    auto b = f(target);
    if (a.size() != b.size()) return false;
    for (int i = 0; i < a.size(); ++i) {
      auto x = a[i], y = b[i];
      if (x.first != y.first) return false;
      if (x.first == 1 && x.second < y.second) return false;
      if (x.first == 2 && x.second > y.second) return false;
    }
    return true;
  }

  vector<pair<int, int>> f(string s) {
    vector<pii> res;
    for (int i = 0; i < s.size(); ++i) {
      if (s[i] == 'L')
        res.push_back({1, i});
      else if (s[i] == 'R')
        res.push_back({2, i});
    }
    return res;
  }
};

func canChange(start string, target string) bool {
  f := func(s string) [][]int {
    res := [][]int{}
    for i, c := range s {
      if c == 'L' {
        res = append(res, []int{1, i})
      } else if c == 'R' {
        res = append(res, []int{2, i})
      }
    }
    return res
  }

  a, b := f(start), f(target)
  if len(a) != len(b) {
    return false
  }
  for i, x := range a {
    y := b[i]
    if x[0] != y[0] {
      return false
    }
    if x[0] == 1 && x[1] < y[1] {
      return false
    }
    if x[0] == 2 && x[1] > y[1] {
      return false
    }
  }
  return true
}

function canChange(start: string, target: string): boolean {
  if (
    [...start].filter(c => c !== '_').join('') !== [...target].filter(c => c !== '_').join('')
  ) {
    return false;
  }
  const n = start.length;
  let i = 0;
  let j = 0;
  while (i < n || j < n) {
    while (start[i] === '_') {
      i++;
    }
    while (target[j] === '_') {
      j++;
    }
    if (start[i] === 'R') {
      if (i > j) {
        return false;
      }
    }
    if (start[i] === 'L') {
      if (i < j) {
        return false;
      }
    }
    i++;
    j++;
  }
  return true;
}

方法二

class Solution:
  def canChange(self, start: str, target: str) -> bool:
    n = len(start)
    i = j = 0
    while 1:
      while i < n and start[i] == '_':
        i += 1
      while j < n and target[j] == '_':
        j += 1
      if i >= n and j >= n:
        return True
      if i >= n or j >= n or start[i] != target[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

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

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

func canChange(start string, target string) bool {
  n := len(start)
  i, j := 0, 0
  for {
    for i < n && start[i] == '_' {
      i++
    }
    for j < n && target[j] == '_' {
      j++
    }
    if i == n && j == n {
      return true
    }
    if i == n || j == n || start[i] != target[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
  }
}

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