Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2337.html
2337. Move Pieces to Obtain a String
- Difficulty: Medium.
- Related Topics: Two Pointers, String.
- Similar Questions: Valid Parentheses, Swap Adjacent in LR String.
Problem
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
andtarget
consist of the characters'L'
,'R'
, and'_'
.
Solution (Java, C++, Python)
-
class Solution { public boolean canChange(String start, String target) { int i = -1; int j = -1; while (true) { while (true) { if (++i >= start.length() || start.charAt(i) != '_') { break; } } while (true) { if (++j >= target.length() || target.charAt(j) != '_') { break; } } if (i == start.length() && j == target.length()) { return true; } if (i == start.length() || j == target.length()) { return false; } if ((start.charAt(i) != target.charAt(j)) || (start.charAt(i) == 'L' ? j > i : i > j)) { return false; } } } } ############ 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; } }
-
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 ############ # 2337. Move Pieces to Obtain a String # https://leetcode.com/problems/move-pieces-to-obtain-a-string/ class Solution: def canChange(self, start: str, target: str) -> bool: if start == target: return True s = [(i, x) for i, x in enumerate(start) if x != "_"] t = [(i, x) for i, x in enumerate(target) if x != "_"] if len(t) != len(s): return False for index, (a, b) in enumerate(zip(s, t)): i, x = a j, y = b if x != y: return False if x == "L": if i < j: return False else: if i > j: return False return True
-
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; }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).