📘 題目敘述
給定一個字串 moves，長度為 n，只會包含 'L'、'R'、'_' 三種字元。
你一開始站在數線上的原點 0。
第 i 次移動時：
- 如果
moves[i] = 'L'，就一定往左走 - 如果
moves[i] = 'R'，就一定往右走 - 如果
moves[i] = '_'，則可以自由選擇往左或往右走
請回傳做完全部 n 次移動後，離原點最遠可以到多遠。
條件限制
1 <= moves.length == n <= 50moves只包含'L'、'R'和'_'
🧠 解題思路
我這題的想法是先統計：
- 一共有幾個
'L' - 一共有幾個
'R' - 一共有幾個
'_'
如果先不管 '_'，那目前位置只會由 L 和 R 的差決定，也就是左右固定步數的淨位移。
而 '_' 最自由的地方在於：
我可以把它們全部往同一個方向選，讓最後位置盡量遠離原點。
所以做法就是：
- 先算固定的左右差距
abs(l - r) - 再把所有
'_'全部補到同一邊
最後答案就是：
abs(l - r) + sp
所有變數
l：字串中'L'的數量r：字串中'R'的數量sp：字串中'_'的數量
🪜 主要流程步驟
1. 先統計三種字元各出現幾次
我先掃過整個字串，分別統計：
'L'出現幾次'R'出現幾次'_'出現幾次
這樣掃完之後，我就知道固定往左、固定往右，以及可自由選方向的步數各有多少。
2. 先看固定的 'L' 和 'R' 會造成多少淨位移
如果只看已經確定方向的移動，那最後位置其實只跟：
- 左走幾步
- 右走幾步
的差有關。
所以固定部分造成的距離就是：
abs(l - r)
例如：
- 如果
L比R多 2 次，那固定部分最後會在左邊 2 格 - 如果
R比L多 3 次，那固定部分最後會在右邊 3 格
總之先取絕對值，就得到目前已經形成的距離。
3. 把所有 '_' 全部往同一個方向選
這題最關鍵的是 '_' 可以自由決定方向。
既然題目要的是離原點最遠的位置，
那最好的做法一定是把所有 '_' 都往同一邊補，讓原本的距離變得更大。
也就是說：
- 如果目前偏左，就把
'_'全部也當成往左 - 如果目前偏右，就把
'_'全部也當成往右 - 就算目前左右一樣多，也可以把
'_'全部選成同一邊
所以這些 '_' 每一個都能再多貢獻 1 的距離，總共就是 sp
4. 最後把兩部分加起來
因此最後答案就是：
abs(l - r) + sp
前半段是固定方向造成的淨距離，
後半段是所有可自由選擇的步數全部往同一邊帶來的額外距離。
⏱️ 複雜度
設 n = moves.length。
- 時間複雜度：
O(n)
我只掃過字串一次。 - 空間複雜度：
O(1)
只用了固定數量的變數。
💻 程式碼實作
class Solution {
public:
int furthestDistanceFromOrigin(string moves) {
int l = 0, r = 0, sp = 0;
for (char c : moves) {
if (c == 'L') {
l++;
} else if (c == 'R') {
r++;
} else {
sp++;
}
}
return abs(l - r) + sp;
}
};
🔗 題目連結
https://leetcode.com/problems/furthest-point-from-origin/