LeetCode [777] Swap Adjacent in LR String

 777. Swap Adjacent in LR String

Medium

In a string composed of 'L', 'R', and 'X' characters, like "RXXLRXRXL", a move consists of either replacing one occurrence of "XL" with "LX", or replacing one occurrence of "RX" with "XR". Given the starting string start and the ending string end, return True if and only if there exists a sequence of moves to transform one string to the other.

 

Example 1:

Input: start = "X", end = "L"
Output: false
Explanation:
We can transform start to end following these steps:
RXXLRXRXL ->
XRXLRXRXL ->
XRLXRXRXL ->
XRLXXRRXL ->
XRLXXRRLX

Example 2:

Input: start = "LLR", end = "RRL"
Output: false

Example 3:

Input: start = "XLLR", end = "LXLX"
Output: false

 

Constraints:

• 1 <= start.length <= 104
• start.length == end.length
• Both start and end will only consist of characters in 'L', 'R', and 'X'.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

class Solution { public boolean canTransform(String start, String end) { if (!start.replace("X", "").equals(end.replace("X", ""))) return false; int p1 = 0; int p2 = 0; while(p1 < start.length() && p2 < end.length()){ // get the non-X positions of 2 strings while(p1 < start.length() && start.charAt(p1) == 'X'){ p1++; } while(p2 < end.length() && end.charAt(p2) == 'X'){ p2++; } //if both of the pointers reach the end the strings are transformable if(p1 == start.length() && p2 == end.length()){ return true; } /*case not exist because # of R/L is equal in two strings // if only one of the pointer reach the end they are not transformable if(p1 == start.length() || p2 == end.length()){ return false; } */ if(start.charAt(p1) != end.charAt(p2)){ return false; } // if the character is 'L', it can only be moved to the left. p1 should be greater or equal to p2. if(start.charAt(p1) == 'L' && p2 > p1){ return false; } // if the character is 'R', it can only be moved to the right. p2 should be greater or equal to p1. if(start.charAt(p1) == 'R' && p1 > p2){ return false; } p1++; p2++; } return true; } }

YMSF

第三轮，给两个string，里面只有l，r，空格。l只能往左移，r只能右移，lr不能交叉。判断第一个string能不能通过以上规则变成第二个。followup：如果lr能最多交叉一次，怎么改。改完又问我如果最多能交叉n次，怎么改。