leetcode 777. Swap Adjacent in LR String | 777. 在LR字符串交换相邻字符双指针

题目

https://leetcode.com/problems/swap-adjacent-in-lr-string/

题解

本来以为是个带 visited 集合的 DFS，一看数据量，居然是 10^4。

然后看了下 hint，Think of the L and R's as people on a horizontal line, where X is a space. The people can't cross each other, and also you can't go from XRX to RXX.，一想，有点像状态机嘛。

详见草稿：

class Solution {
    public boolean canTransform(String start, String end) {
        int i = 0;
        int j = 0;
        while (true) {
            while (i < start.length() && start.charAt(i) == 'X') i  ;
            while (j < end.length() && end.charAt(j) == 'X') j  ;

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

            if (i < start.length() && j < end.length() && start.charAt(i) == end.charAt(j)) { // 两字母相同
                if (start.charAt(i) == 'L') { // 均为L
                    if (i < j) return false;
                } else { // 均为R
                    if (j < i) return false;
                }
                i  ;
                j  ;
            } else { // 两字母不同
                return false;
            }
        }
    }
}

这篇好文章是转载于：学新通技术网