777. Swap Adjacent in LR String
Previous209. Minimum Size Subarray SumNextlintcode 1375 · Substring With At Least K Distinct Characters
Last updated
Was this helpful?
Last updated
Was this helpful?
ref:
ref:
https://www.cnblogs.com/grandyang/p/9001474.html
T: O(n)
S: O(1)
class Solution {
public boolean canTransform(String start, String end) {
// remove X, start and end should the same
if (!start.replace("X", "").equals(end.replace("X", ""))) {
return false;
}
int n = start.length();
int sIdx = 0;
int eIdx = 0;
while (sIdx < n && eIdx < n) {
// 遇到 'X' 略過
while (sIdx < n && start.charAt(sIdx) == 'X') {
sIdx++;
}
while (eIdx < n && end.charAt(eIdx) == 'X') {
eIdx++;
}
// 可能前面 while 最後跳出時剛好在 n
if (sIdx == n && eIdx == n) { //代表跑完了
return true;
}
if (sIdx == n || eIdx == n) { //一長一短, 一定錯
return false;
}
char s = start.charAt(sIdx);
char e = end.charAt(eIdx);
if (s != e) { // 照理去掉 X 後, start end 指向同一個字
return false;
}
if (s == 'L' && eIdx > sIdx) { // check 位置, L eidx 應該會越來越小
return false;
}
if (s == 'R' && eIdx < sIdx) { // check 位置, L eidx 應該會越來越大
return false;
}
sIdx++;
eIdx++;
}
return true;
}
}
/*
1.
"XL" with "LX", or replacing one occurrence of
"RX" with "XR"
"XL" with "LX" => we can get L will continuously move to left
"RX" with "XR" => we can get R will continuously move to right
2.
so in correct case, after swaping, R shoud in right side (end index > start index)
RXXLRXRXL (start index: 0)
p
XRLXXRRLX (end index: 1)
p
and after change, the start[start index] == end[end index] => start[0] == end[1] == R
3.
so in correct case, after swaping, L shoud in left side (end index < start index)
RXXLRXRXL (start index: 3)
p
XRLXXRRLX (end index: 2)
p
and after change, the start[start index] == end[end index] => start[3] == end[2] == L
4.
one more noticed!
remove X, they should the same
"RXXLRXRXL" => RLRRL
"XRLXXRRLX" => RLRRL
一開始的判斷
if (!start.replace("X", "").equals(end.replace("X", ""))) {
return false;
T: O(n)
S: O(1)
*/