Java strictly in place solution, no temp variable for swap


  • 0
    B

    Use XOR bitwise swap to reduce the extra temp variable in many other solutions.

        public void reverseWords(char[] s) {
            //first reverse whole array
            int p1 = 0, p2 = s.length - 1;
            while(p1 < p2) {
                s[p1] = (char) (s[p1] ^ s[p2]);
                s[p2] = (char) (s[p2] ^ s[p1]);
                s[p1] = (char) (s[p2] ^ s[p1]);
                p1++;
                p2--;
            }
            //then reverse each word
            int st = 0, en = 0; //start and end of a word
            while(en < s.length) {
                while(en < s.length && s[en] != ' ') {
                    en++;
                }
                en--;
                while(st < en) {
                    s[st] = (char) (s[st] ^ s[en]);
                    s[en] = (char) (s[en] ^ s[st]);
                    s[st] = (char) (s[st] ^ s[en]);
                    st++;
                    en--;
                }
                while(st < s.length && s[st] != ' ') {
                    st++;
                }
                st++;
                en = st + 1;
            }
        }
    

Log in to reply
 

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