LeetCode -- 777. 在LR字符串中交换相邻字符

发布时间 2023-08-21 09:38:24作者: 深渊之巅

 

给两种不同元素,可以和第三种元素交换位置,L只能向左走,R只能向右走,问start数组可否经过某些变换变换到end。

经典双指针算法。

class Solution {
public:
    bool canTransform(string start, string end) {
        int n = start.size();
        int i = 0, j = 0;
        while(true) {
            while(i < n && start[i] == 'X') i ++ ;
            while(j < n && end[j] == 'X') j ++ ;
            if(i == n && j == n) return true;
            if(i == n || j == n || start[i] != end[j]) return false;
            if(start[i] == 'L' && i < j) return false;
            if(start[i] == 'R' && i > j) return false;
            i ++ , j ++ ;
        }
    }
};