My O(n) time O(1) space C++ code (wrong solution)


  • 0
    C

    it is a wrong solution so I decided to delete it, as for the details, please see the discuses below, thank you.


  • -1

    I think if you do unsafe stuff like that, you should say so, at least in order to not confuse newbies. Your code fails for example for s="bbxx", t="iipp", for which it returns true.


  • 0
    C

    maybe my method not work on this problem... the testing data is a little bit weak...


  • 0

    Now you fail for example s="bln", t="cip"


  • 0

    I think it is a clever solution. But not safe. Since 2 sets of n numbers (multiply together to be the same) and (add up together to be the same) is not unique.


  • 0
    C

    Yeah, the basic idea is to use many classifiers to vote whether the two sequence have the same characters,so that we can get an O(1)space answer... this is not the first version, the first version used "^" and "+" to vote, after noticed by StefanPochMann I changed "^" to "*" but still not work ... I also wanted to use "&" and "|" but I can not prove my idea is OK for this...


  • 0

    @chao15 I already have test cases where the two strings are not anagrams but do have the same length, sum, product, "^", "&" and "|" :-)


  • 0
    C

    what a pity... So there isn't a O(1) space solution for this problem? I will delete my code for not mistake anybody, thank you for your notify:)


  • 0
    This post is deleted!

  • 0

    "So there isn't a O(1) space solution for this problem?"

    Not in a strict theoretical way, as apparently only regular languages are truly fully O(1) space and the anagrams language isn't regular. But in practice / real life, I think it's legitimate to call the letter-counting solutions O(1) space.

    You didn't have to delete your solution, a clarification would've been enough and I think it's still kinda interesting. With randomization and repetition it could also be made pretty safe. Quoting Wikipedia for something related:

    If the correct answer is YES and the algorithm is run n times with the result of each run statistically independent of the others, then it will return YES at least once with probability at least 1 − 2−n. So if the algorithm is run 100 times, then the chance of it giving the wrong answer every time is lower than the chance that cosmic rays corrupted the memory of the computer running the algorithm.


Log in to reply
 

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