2337. 移动片段得到字符串

🟠   🔖  双指针 字符串  🔗 力扣 LeetCode

题目

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 stringstart 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 <= 10^5
• start and target consist of the characters 'L', 'R', and '_'.

题目大意

给你两个字符串 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 <= 10^5
• start 和 target 由字符 'L'、'R' 和 '_' 组成

解题思路

本题要求验证是否可以通过移动 'L' 和 'R' 从字符串 start 变为字符串 target，移动规则是：

1. 'L' 可以向左移动，但不能向右；
2. 'R' 可以向右移动，但不能向左；
3. start 和 target 的空位 _ 可以被占据。

如果 start 移动后可以得到 target，必须满足以下要求：

• start 和 target 的 'L' 和 'R' 的相对顺序必须一致。换句话说，start 和 target 去掉 '_' 后必须有相同的字符序列，否则无法通过任何移动变换得到。
• 对于 'L'：start 中的 'L' 的下标必须大于等于 target 中对应 'L' 的下标，因为 'L' 只能向左移动。
• 对于 'R'：start 中的 'R' 的下标必须小于等于 target 中对应 'R' 的下标，因为 'R' 只能向右移动。

因此，可以使用两个指针分别遍历 start 和 target，逐一验证每个 'L' 和 'R' 的位置关系是否符合上述规则。

1. 从 start 和 target 中去掉所有的 '_'，如果剩下的字符序列不同，直接返回 false。
2. 使用双指针遍历 start 和 target：
   • 如果遇到 'L'，检查 start 中的索引是否大于等于 target 中的索引。
   • 如果遇到 'R'，检查 start 中的索引是否小于等于 target 中的索引。
3. 如果所有的字符都满足规则，返回 true；否则返回 false。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串的长度，双指针遍历字符串 start 和 target，每个字符最多遍历一次。
• 空间复杂度：O(1)，仅使用了固定数量的变量，没有额外空间开销。

代码

/**
 * @param {string} start
 * @param {string} target
 * @return {boolean}
 */
var canChange = function (start, target) {
	let n = start.length;
	let i = 0,
		j = 0;

	// 双指针遍历
	while (i < n || j < n) {
		// 跳过 start 和 target 中的空位 '_'
		while (i < n && start[i] === '_') i++;
		while (j < n && target[j] === '_') j++;

		// 如果两者同时结束，说明匹配成功
		if (i === n && j === n) return true;

		// 如果只有一个结束，说明匹配失败
		if (i === n || j === n) return false;

		// 当前字符必须一致，否则匹配失败
		if (start[i] !== target[j]) return false;

		// 验证移动规则
		if (start[i] === 'L' && i < j) return false; // 'L' 不能向右移动
		if (start[i] === 'R' && i > j) return false; // 'R' 不能向左移动

		// 移动指针
		i++;
		j++;
	}

	return true;
};

相关题目

题号	标题	题解	标签	难度	力扣
20	有效的括号	[✓]	栈 字符串	🟢	🀄️ 🔗
777	在LR字符串中交换相邻字符		双指针 字符串	🟠	🀄️ 🔗