Fast XOR Simple JAVA Solution


  • 2

    Only use one iteration and constant space.

    public class Solution {
        public char findTheDifference(String s, String t) {
            int res = (int)t.charAt(0);
            for(int i = 0; i < s.length(); ++i){
                res = res^(int)s.charAt(i);
                res = res^(int)t.charAt(i+1);
            }
            return (char)res;
        }
    }
    

  • 0
    N

    You're the best sulotion I found. :).

    (I'm also use the xor to find out the additional one, but my solution will create 2 new char array, which is waste the memory. :P) )

    Thanks for the sharing.


  • 1
    M

    Wow, it is very nice to use XOR. Pretty smart! Based on your solution, I changed the code a little bit.

    public class Solution {
        public char findTheDifference(String s, String t) {
            char[] sArr = s.toCharArray();
            char[] tArr = t.toCharArray();
            
            char res = tArr[sArr.length];
            for(int i = 0; i < sArr.length; ++i)
                res ^= sArr[i]^tArr[i];
    
            return res;
        }
    }
    

  • 1
    S

    There really isn't any reason to convert to int, as chars can already be treated as ints.

        public char findTheDifference(String s, String t) {
            char ans = t.charAt(t.length() - 1);
            for(int i = 0; i < s.length(); i++){
                ans ^= s.charAt(i) ^ t.charAt(i);
            }
            return ans;
        }
    

    @ming328 toCharArray() requires copying the String's internal array, which increase time and space complexity (O(n) for each array). charAt(n) is O(1) so it is best to just work with it even if it is slightly more ugly :)


  • 1
    M

    @strmrdr I was just used to do so as I saw the post here (optimization by using .toCharArray instead of .charAt). I think you are right as someone else also pointed out in the post here. I think I need to do some research but thanks for letting me know :)


Log in to reply
 

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