5ms Solution in Java Using Arithmetic Operation,O(1) space,O(n) time


  • -1
    H

    Previous solutions are all using HashMap or Array to record message,which is unnecessary.With few variables and three operation( * and + and XOR),we can easily solve the problem.Here is my code.
    To avoid Integer Overflow,I make some reduction.

    public class Solution {
        public boolean isAnagram(String s, String t) {
            if(s.length() != t.length())
                return false;
            char[] sArray = s.toCharArray();
            char[] tArray = t.toCharArray();
            int sSum = 0;
            int tSum = 0;
            long sMul = 1;
            long tMul = 1;
            int sXOR = 0;
            int tXOR = 0;
            for(int i = 0;i<s.length();i++){
                sSum += sArray[i];
                sMul *= sArray[i]-'a'+1;
                sXOR ^= sArray[i];
                
                tSum += tArray[i];
                tMul *= tArray[i]-'a'+1;
                tXOR ^= tArray[i];
                
            }
            return (sSum == tSum) && (sMul == tMul) &&(sXOR == tXOR);
            
        }
    }
    

    Perhaps it's not straight-forward,let me make some explaination.
    Assume we have two Strings:"ab" and "cd"
    Firstly I figure out:

                sSum = a+b,tSum = c+d
                sMul = a*b,tMul = c*d
    

    if sSum equals tSum ,and sMul equals tMul,we get the equations:

                 a+b = c+d
                 a*b = c*d
    

    After simplification we get the equation

                 a*a + b*b = c*c +d*d
    

    We can prove that once the equation is satisfied,a is either c or d,and b is either d or c.
    Great appreciation for @ManuelP 's counter-examples


  • 0
    S

    @Horanol could explain the sum and mul ?


  • 0

    Of course this is wrong, just like every other similar attempt. For example, it falsely claims that "ppppppphx" is an anagram of "ppppppppp".


  • -1
    H

    @ManuelP
    Not wrong.Just the product of all the chars causes Integer overflow(see the sMul and tMul variables are type of int).It can be solved by occasionally reducing the product,but it's somewhat awkward.


  • 0
    H

    @sse.michael
    sum is the sum of the char array,mul is the product of the char array.Is that clear to you?


  • 0

    @Horanol No, it is wrong. I already gave you a counter-example proving that it's wrong.

    And no, you can't fix it like you think you can. Try it, show the code, and I'll give you a counter-example for that as well.


  • 0

    Actually you unsurprisingly already fail even without overflow, for example your code falsely claims "bln" is an anagram of "cip".


  • 0
    H

    @ManuelP
    Well,you're right,just addition and multiplication cannot guarantee the result.Previously I also included XOR operation in my code,but it seemed redundant to pass test cases of Leetcode,so I just gave it up.But it seems essential to pass your test. So now I've changed my code.Great appreciation for your counter-examples.


  • 0

    Now you for example falsely claim that "aanr" is an anagram of "abkt".

    Wondering how long it'll take you to accept that this kind of approach is fundamentally wrong :-)


  • -1
    H

    @ManuelP
    I've changed the type from int to float to avoid the truncation of Integer when reducing the product and passed your test.
    Of cause I cannot perfectly prove that in math,but by intuition I think it's right :)


  • 0

    Now you for example fail "aajmv", "abilw".


  • -1
    H

    @ManuelP
    I found another way to delay overflow
    And perhaps XOR operation is unneeded


  • 2

    Now you fail for example "cub", "rag".


Log in to reply
 

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