本文屬于「征服LeetCode」系列文章之一，這一系列正式開始于2021/08/12。由于LeetCode上部分題目有鎖，本系列將至少持續(xù)到刷完所有無鎖題之日為止；由于LeetCode還在不斷地創(chuàng)建新題，本系列的終止日期可能是永遠。在這一系列刷題文章中，我不僅會講解多種解題思路及其優(yōu)化，還會用多種編程語言實現(xiàn)題解，涉及到通用解法時更將歸納總結(jié)出相應的算法模板。
為了方便在PC上運行調(diào)試、分享代碼文件，我還建立了相關(guān)的倉庫：https://github.com/memcpy0/LeetCode-Conquest。在這一倉庫中，你不僅可以看到LeetCode原題鏈接、題解代碼、題解文章鏈接、同類題目歸納、通用解法總結(jié)等，還可以看到原題出現(xiàn)頻率和相關(guān)企業(yè)等重要信息。如果有其他優(yōu)選題解，還可以一同分享給他人。
由于本系列文章的內(nèi)容隨時可能發(fā)生更新變動，歡迎關(guān)注和收藏征服LeetCode系列文章目錄一文以作備忘。
給你兩個字符串?start?和?target?，長度均為?n?。每個字符串?僅?由字符?'L'、'R'?和?'_'?組成，其中：
- 字符?
'L'?和?'R'?表示片段，其中片段?'L'?只有在其左側(cè)直接存在一個?空位?時才能向?左?移動，而片段?'R'?只有在其右側(cè)直接存在一個?空位?時才能向?右?移動。 - 字符?
'_'?表示可以被?任意?'L'?或?'R'?片段占據(jù)的空位。
如果在移動字符串?start?中的片段任意次之后可以得到字符串?target?，返回?true?；否則，返回?false?。
示例 1：
輸入：start = "_L__R__R_", target = "L______RR" 輸出：true 解釋：可以從字符串 start 獲得 target ，需要進行下面的移動： - 將第一個片段向左移動一步，字符串現(xiàn)在變?yōu)?"L___R__R_" 。 - 將最后一個片段向右移動一步，字符串現(xiàn)在變?yōu)?"L___R___R" 。 - 將第二個片段向右移動三步，字符串現(xiàn)在變?yōu)?"L______RR" 。 可以從字符串 start 得到 target ，所以返回 true 。
示例 2：
輸入：start = "R_L_", target = "__LR" 輸出：false 解釋：字符串 start 中的 'R' 片段可以向右移動一步得到 "_RL_" 。 但是，在這一步之后，不存在可以移動的片段，所以無法從字符串 start 得到 target 。
示例 3：
輸入：start = "_R", target = "R_" 輸出：false 解釋：字符串 start 中的片段只能向右移動，所以無法從字符串 start 得到 target 。
提示：
n == start.length == target.length1 <= n <= 10^5-
start?和?target?由字符?'L'、'R'?和?'_'?組成
解法 雙指針
首先，無論怎么移動，由于
L
L
L 和
R
R
R 無法互相穿過對方，那么去掉 _ 后的剩余字符應該是相同的，否則返回
f
a
l
s
e
false
false 。然后用雙指針從左向右遍歷
start
\textit{start}
start 和
target
\textit{target}
target ，分類討論：文章來源：http://www.zghlxwxcb.cn/news/detail-663384.html
- 如果當前字符為 L L L 且 i < j i<j i<j ，由于 L L L 由于無法向右移動，返回 f a l s e false false ；
- 如果當前字符為 R R R 且 i > j i>j i>j ，由于 R R R 由于無法向左移動，返回 f a l s e false false 。
- 遍歷完，若中途沒有返回 f a l s e false false 就返回 t r u e true true 。
class Solution {
public:
bool canChange(string start, string target) {
int n = start.size();
int i = 0;
for (int j = 0; j < n; ++j) {
if (target[j] == '_') continue;
while (i < n && start[i] == '_') ++i;
if (i == n ||
start[i] != target[j] || // 當前字符不同
i != j && (start[i] == 'L') == (i < j))
return false; // 順序不符合
++i;
}
while (i < n)
if (start[i++] != '_') return false;
return true;
}
};
復雜度分析：文章來源地址http://www.zghlxwxcb.cn/news/detail-663384.html
- 時間復雜度： O ( n ) \mathcal{O}(n) O(n) ，其中 n n n 為 start \textit{start} start 的長度。
- 空間復雜度： O ( 1 ) \mathcal{O}(1) O(1) 。
到了這里，關(guān)于LeetCode 2337. Move Pieces to Obtain a String【字符串,雙指針】1693的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
