2337. 移动片段得到字符串

问题

给你两个字符串 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' 和 '_' 组成

答案

var canChange = function(start, target) {
    // Check if the number of 'L' and 'R' are the same in start and target
    if (start.replace(/_/g, '').split('').sort().join('') !== target.replace(/_/g, '').split('').sort().join('')) {
        return false;
    }

    // Check if the sequence of 'L' and 'R' in start can be transformed to the sequence in target
    let i = 0, j = 0;
    while (i < start.length && j < target.length) {
        while (i < start.length && start[i] === '_') i++;
        while (j < target.length && target[j] === '_') j++;

        if (i === start.length && j === target.length) return true;
        if (i === start.length || j === target.length) return false;

        if (start[i] !== target[j]) return false;
        if (start[i] === 'L' && i < j) return false;
        if (start[i] === 'R' && i > j) return false;

        i++;
        j++;
    }

    while (i < start.length && start[i] === '_') i++;
    while (j < target.length && target[j] === '_') j++;
    return i === start.length && j === target.length;
};

结果

分析

这个函数的主要逻辑是通过比较start和target中的’L’和’R’字符的位置和数量来判断start是否可以通过移动字符转换为target。下面是对每段代码的详细解释：

JavaScript

var canChange = function(start, target) {

这一行定义了一个名为canChange的函数，该函数接受两个参数：start和target。

if (start.replace(/_/g, '').split('').sort().join('') !== target.replace(/_/g, '').split('').sort().join('')) {
    return false;
}

这段代码首先移除start和target字符串中的所有空位字符（‘_’），然后将剩余的字符排序并组合成新的字符串。如果排序后的字符串不相同，那么函数返回false，表示start不能转换为target。

let i = 0, j = 0;
while (i < start.length && j < target.length) {
    while (i < start.length && start[i] === '_') i++;
    while (j < target.length && target[j] === '_') j++;

这段代码定义了两个指针i和j，分别用于遍历start和target字符串。在每次循环开始时，指针会跳过所有的空位字符。

if (i === start.length && j === target.length) return true;
if (i === start.length || j === target.length) return false;

这段代码检查是否已经遍历完所有的非空位字符。如果两个字符串的所有非空位字符都已经被遍历，那么函数返回true。如果只有一个字符串的非空位字符被遍历完，那么函数返回false。

if (start[i] !== target[j]) return false;
if (start[i] === 'L' && i < j) return false;
if (start[i] === 'R' && i > j) return false;

这段代码比较start和target中当前位置的字符。如果字符不同，或者字符的移动方向不对（例如’L’向右移动或’R’向左移动），则返回false。

i++;
j++;

这段代码将两个指针向前移动一位，以便在下一次循环中比较下一个字符。

while (i < start.length && start[i] === '_') i++;
while (j < target.length && target[j] === '_') j++;
return i === start.length && j === target.length;

这段代码在遍历完所有非空位字符后，跳过剩余的空位字符。如果所有的字符都被正确地处理了，那么函数返回true。

官方解答

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

作者：力扣官方题解
链接：https://leetcode.cn/problems/move-pieces-to-obtain-a-string/solutions/1855012/yi-dong-pian-duan-de-dao-zi-fu-chuan-by-0j7py/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

官方答案分析

这个函数的主要逻辑是通过比较start和target中的’L’和’R’字符的位置和数量来判断start是否可以通过移动字符转换为target。下面是对每段代码的详细解释：

var canChange = function(start, target) {

这一行定义了一个名为canChange的函数，该函数接受两个参数：start和target。

const n = start.length;
let i = 0, j = 0;

这两行代码初始化了三个变量：n是字符串的长度，i和j是用于遍历字符串的指针。

while (i < n && j < n) {
    while (i < n && start[i] === '_') {
        i++;
    }
    while (j < n && target[j] === '_') {
        j++;
    }

这段代码使用两个内部循环跳过start和target中的空位字符（‘_’）。

if (i < n && j < n) {
    if (start[i] !== target[j]) {
        return false;
    }

这段代码比较start和target中当前位置的字符。如果字符不同，那么函数返回false。

const c = start[i];
if ((c === 'L' && i < j) || (c === 'R' && i > j)) {
    return false;
}

这段代码检查字符的移动方向。如果’L’字符在start中的位置小于在target中的位置，或者’R’字符在start中的位置大于在target中的位置，那么函数返回false。

i++;
j++;

这段代码将两个指针向前移动一位，以便在下一次循环中比较下一个字符。

while (i < n) {
    if (start[i] !== '_') {
        return false;
    }
    i++;
}
while (j < n) {
    if (target[j] !== '_') {
        return false;
    }
    j++;
}

这段代码在遍历完所有非空位字符后，检查start和target中是否还有剩余的非空位字符。如果有，那么函数返回false。

return true;

如果所有的字符都被正确地处理了，那么函数返回true。

反思

官方使用了两个指针i和j来同时遍历start和target字符串，并且在遍历过程中跳过了所有的空位字符。这样代码只需要遍历一次字符串，而不是像我之前的解决方案那样需要遍历两次。此外，官方代码在处理完所有非空位字符后，会额外检查start和target中是否还有剩余的非空位字符。这个额外的检查可以提前结束函数的执行，从而提高性能，代码更加精简和高效