My C solution: time O(n), space O(1) passed


  • 0
    S
    1. There are some conditions:
      A. input strings(s, t) were valid Anagram.
      B. x ∈ string(s), y ∈ string(t) ∑ (x)i == ∑ (y)i .
      C. x ∈ string(s), y ∈ string(t) Π (x)i == Π (y)i .

    2. And a statement:
      D. set1{x1,y1}, set2{x2,y2}; x1,x2,y1,y2 ∈ ['a', +∞ ]; if x1y1 == x2y2, x1+y1 == x2+y2; then set1==set2.

    3. Conditional relation:
      I. A => B
      II. A => C
      III. B+C <=> A (why?) maybe you are question why 'B+C' is sufficient and necessary conditions of 'A'. my answer is that the Statement 'D' was a True Statement. I will prove it now.

    4. Prove:
      First. We assume Statement 'D' was a False Statement. So There are positive integer 'a' and 'b' made the following equation be established:
      x1 = x2 + a ( a != 0);
      y1 = y2 + b ( b != 0);
      Note: when a =0 and b = 0, set1(x1, y1)=set2(x2, y2).
      Second. Let's bring it into known conditions:
      x1 + y1 = x2 + y2
      =>(x2+a) + (y2+b) = x2 + y2
      => a+b = 0
      => a=-b

      x1y1 = x2y2
      =>(x2+a)(y2+b) = x2y2
      =>x2y2 + ay2 + bx2 + ab = x2y2
      => ay2 + bx2 +ab = 0
      ∵ a=-b
      => -by2 + bx2 - b^2 = 0
      ∵ a != 0 , b != 0
      => -y2 + x2 - b = 0
      => x2 = y2 + b
      ∵ y1 = y2 + b
      => y1 = x2
      Corollaries:
      => x1 = y2
      At last. We Proved Set1(x1, y1)=Set2(x2, y2).
      However, Statement 'D' was a True Statement!

    bool isAnagram(char* s, char* t) {
        int b1 = 0, b2 = 0;
        int c1 = 1, c2 = 1;
        int len1 = (int)strlen(s);
        int len2 = (int)strlen(t);
        if(len1 != len2){
            return false;
        }
        int i = 0;
        while(*(s+i) != '\0'){
            b1 += *(s+i);
            b2 += *(t+i);
            c1 *= *(s+i);
            c2 *= *(t+i);
            i++;
        }
        return (b1==b2)&&(c1==c2);
    }
    

Log in to reply
 

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