# 头脑风暴

## Swap Adjacent in LR String

* 给定2个string, start and end, 只包含L, X, R char
* 可以replace "XL" with "LX", replace "RX" with "XR", 求问start 是否能transform成end string
* 一开始自然的想到了word ladder的思路，给定source and dest求问最短路径
* 暴力写了个BFS结果TLE了
  * start: "XXRXXXXXXXRXRXXXLXXLXXLXXXXXRXXXXXXXXLXX"
  * end: "XXXRXXXXRXXXXXXRXXXLXXXXXXXLXXLXXRXXLXXX"

```
class Solution {
    public boolean canTransform(String start, String end) {
        if (start.equals(end)) return true;
        Queue<String> queue = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        queue.offer(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            String cur = queue.poll();
            for (int i = 0; i < cur.length() - 1; i++) {
                if (cur.substring(i, i + 2).equals("XL")) {
                    String next = cur.substring(0, i) + "LX" + cur.substring(i + 2);
                    if (next.equals(end)) return true;
                    if (visited.contains(next)) continue;
                    queue.offer(next);
                    visited.add(next);
                }
                if (cur.substring(i, i + 2).equals("RX")) {
                    String next = cur.substring(0, i) + "XR" + cur.substring(i + 2);
                    if (next.equals(end)) return true;
                    if (visited.contains(next)) continue;
                    queue.offer(next);
                    visited.add(next);
                }
            }
        }
        return false;
    }
}
```

* 然后就去Discuss里看了其它答案，发现这题是个数学推演题
* since we can only move R to the right RX->XR, move L to the left, XL->LX L and R can never cross each other
* just skip X character and compare position of L and R in 2 strings&#x20;
* for start\[i] = end\[j] = L, check i>=j, 因为 L只能左移&#x20;
* start\[i] = end\[j] = R, check i<=j， 因为R只能右移
* 转换成了two pointer
* 这里有个非常tricky的case
  * start:"XXRXLXRXXX"&#x20;
  * end: "XXRLXXXXXR"
* 因为end的最后一个char是R, 但是start最后一个R之后还有一堆X, 所以不能简单的写while (p1 < n && p2 < n), 需要特殊处理p1==n和p2==n的情况

```
class Solution {
    public boolean canTransform(String start, String end) {
        if (start.length() != end.length()) return false;
        int n = start.length();
        int p1 = 0, p2 = 0;
        while (p1 <= n && p2 <= n) {
            while (p1 < n && start.charAt(p1) == 'X') p1++;
            while (p2 < n && end.charAt(p2) == 'X') p2++;
            if (p1 == n && p2 == n) return true;
            if (p1 == n) {
                while (p2 < n && end.charAt(p2) == 'X') p2++;
                return p2 == n;
            }
            if (p2 == n) {
                while (p1 < n && start.charAt(p1) == 'X') p1++;
                return p1 == n;
            }
            if (start.charAt(p1) != end.charAt(p2)) return false;
            if (start.charAt(p1) == 'L' && p1 < p2) return false;
            if (start.charAt(p1) == 'R' && p1 > p2) return false;
            p1++;
            p2++;
        }
        return p1 == n && p2 == n;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://syjohnson11.gitbook.io/leetcode/9_math/tou-nao-feng-bao.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.