Leetcode-每日一题777. 在LR字符串中交换相邻字符

2023-02-06 98

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 在去掉所有X的两个字符串序列不相等，则他们永远不可能通过操作变成相同，例如：start：LXR，end：RXL，不管你怎么移动都不可能使两个字符串相同。

题目链接：点击跳转

思路

方法一、双指针

题目的意思是给你一个两个字符串你的R只能向右移动，L只能向左移动，并且只能旁边有X才能移动，能否将start字符串操作后变成end字符串。

双指针的做法：一个指针i指向start的开头，指针j指向end的开头，跳过所有X字符，去进行判断。

失败的条件：

在去掉所有X的两个字符串序列不相等，则他们永远不可能通过操作变成相同，例如：start：LXR，end：RXL，不管你怎么移动都不可能使两个字符串相同。

L只能向左移动，所以如果我要移动到end的L对应位置j在i的后面我就不能移动，例如：start：LXL，end：XLL

同理，R只能向右移动，如果我要移动到end的R对应位置j在i的前面我就不能移动，例如：start：XRR，end：RXR

代码示例

func canTransform(start string, end string) bool {
    strLen := len(start)
    i, j := 0, 0
    for i < strLen && j < strLen {
        for i < strLen && start[i] == 'X' {
            i++
        }
        for j < strLen && end[j] == 'X' {
            j++
        }
        //防止栈溢出
        if i == strLen || j == strLen{
            break
        }
        if start[i] != end[j]{
            return false
        }
        if (start[i] == 'L' && i < j) || (end[j] == 'R' && i > j){
            return false
        }
        i++
        j++
    }
    //如果有指针先跑完，需要将另一个也同样跑完，跳过所有X
    for i < strLen && start[i] == 'X' {
        i++
    }
    for j < strLen && end[j] == 'X' {
        j++
    }
    //跑完两个指针发现还有字符剩余，那就是两个去掉X的字符串不相同
    if i != strLen || j != strLen{
        return false
    }
    return true
}