Question

2337. Move Pieces to Obtain a String

中文文档

Description

You are given two strings start and target, both of length n. Each string consists only of the characters 'L', 'R', and '_' where:

• The characters 'L' and 'R' represent pieces, where a piece 'L' can move to the left only if there is a blank space directly to its left, and a piece 'R' can move to the right only if there is a blank space directly to its right.
• The character '_' represents a blank space that can be occupied by any of the 'L' or 'R' pieces.

Return true _if it is possible to obtain the string_ target_ by moving the pieces of the string _start_ any number of times_. Otherwise, return false.

 

Example 1:

Input: start = "_L__R__R_", target = "L______RR"
Output: true
Explanation: We can obtain the string target from start by doing the following moves:
- Move the first piece one step to the left, start becomes equal to "L___R__R_".
- Move the last piece one step to the right, start becomes equal to "L___R___R".
- Move the second piece three steps to the right, start becomes equal to "L______RR".
Since it is possible to get the string target from start, we return true.

Example 2:

Input: start = "R_L_", target = "__LR"
Output: false
Explanation: The 'R' piece in the string start can move one step to the right to obtain "_RL_".
After that, no pieces can move anymore, so it is impossible to obtain the string target from start.

Example 3:

Input: start = "_R", target = "R_"
Output: false
Explanation: The piece in the string start can move only to the right, so it is impossible to obtain the string target from start.

 

Constraints:

• n == start.length == target.length
• 1 <= n <= 105
• start and target consist of the characters 'L', 'R', and '_'.

Solutions

Solution 1

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;
}

Solution 2

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;
  }
}