Swap Adjacent in LR String


  • 0

    Click here to see the full article post


  • 0
    D

    Hello @awice,
    Thanks for the explanation. Could you please clarify this logic- 'Additionally, the n-th 'L' can never go to the right of it's original position, and similarly the n-th 'R' can never go to the left of it's original position. We'll call this "accessibility"'

    And also this( my own test case) test case: start - 'LXXLXRLXLX', end - 'XLLXRXLXLX' should return True as per my understanding. But it returns false as per above given solution. Could you help me with this.

    Thanks,
    Dharshini


  • 0
    Y

    @DharshiniPriya You example should return false, because the rule is XL -> LX for start string, not the other way around.


  • 0

    1-pass implementation:
    @vegito2002 said in Simple Java one pass O(n) solution with explaination:

    class Solution {
        public boolean canTransform(String start, String end) {
            if (start.length () != end.length ())
                return false;
            char[] chs = start.toCharArray (), che = end.toCharArray ();
            int i = -1, j = -1;
            while (++i < chs.length && ++j < che.length) {
                // only care about L or R, skip X
                while (i < chs.length && chs[i] == 'X') i++;
                while (j < che.length && che[j] == 'X') j++;
                // number of L/R is not equal in both strings, can't transform
                if ((i < chs.length) ^ (j < che.length)) return false;
                if (i < chs.length && j < che.length) {
                    // mismatched L/R
                    if (chs[i] != che[j]) return false;
                    // L can only move left
                    if (chs[i] == 'L' && i < j) return false;
                    // R can only move right
                    if (chs[i] == 'R' && i > j) return false;
                }
            }
            return true;
        }
    }
    

  • 0
    B

    This should be hard. Not medium.


  • 0
    Z

    The space complexity of Approach #2 should be O(N), since it transfers the string to char array


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.