move-pieces-to-obtain-a-string

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two strings <code>start</code> and <code>target</code>, both of length <code>n</code>. Each string consists only of the characters <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, and <code>&#39;_&#39;</code> where:

<ul>
	<li>The characters <code>&#39;L&#39;</code> and <code>&#39;R&#39;</code> represent pieces, where a piece <code>&#39;L&#39;</code> can move to the left only if there is a blank space directly to its left, and a piece <code>&#39;R&#39;</code> can move to the right only if there is a blank space directly to its right.</li>
	<li>The character <code>&#39;_&#39;</code> represents a blank space that can be occupied by any of the <code>&#39;L&#39;</code> or <code>&#39;R&#39;</code> pieces.</li>
</ul>

Return <code>true</code> if it is possible to obtain the string <code>target</code> by moving the pieces of the string <code>start</code> any number of times. Otherwise, return <code>false</code>.

&nbsp;
Example 1:

<pre>
Input: start = &quot;_L__R__R_&quot;, target = &quot;L______RR&quot;
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 &quot;L___R__R_&quot;.
- Move the last piece one step to the right, start becomes equal to &quot;L___R___R&quot;.
- Move the second piece three steps to the right, start becomes equal to &quot;L______RR&quot;.
Since it is possible to get the string target from start, we return true.
</pre>

Example 2:

<pre>
Input: start = &quot;R_L_&quot;, target = &quot;__LR&quot;
Output: false
Explanation: The &#39;R&#39; piece in the string start can move one step to the right to obtain &quot;_RL_&quot;.
After that, no pieces can move anymore, so it is impossible to obtain the string target from start.
</pre>

Example 3:

<pre>
Input: start = &quot;_R&quot;, target = &quot;R_&quot;
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.</pre>

&nbsp;
Constraints:

<ul>
	<li><code>n == start.length == target.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>start</code> and <code>target</code> consist of the characters <code>&#39;L&#39;</code>, <code>&#39;R&#39;</code>, and <code>&#39;_&#39;</code>.</li>
</ul>

canChange

Move Pieces to Obtain a String

Valid Parentheses

valid-parentheses

有效的括号

Swap Adjacent in LR String

swap-adjacent-in-lr-string

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

Two Pointers

String

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

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

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

&nbsp;

示例 1：

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

示例 2：

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

示例 3：

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

&nbsp;

提示：

<ul>
	<li><code>n == start.length == target.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>start</code> 和 <code>target</code> 由字符 <code>'L'</code>、<code>'R'</code> 和 <code>'_'</code> 组成</li>
</ul>