Timeline for Determining if two words are anagrams
Current License: CC BY-SA 3.0
43 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 10, 2015 at 4:43 | comment | added | JcT |
Glad to help! Regarding performance, this code now performs pretty well against the prime hashing technique when you test against values that aren't anagrams; which, to be fair, most aren't. There is a potential speed improvement if you set counts to an array with 26 zeros (you can remove the || in the first loop, and I think some engines can optimise better knowing the length and type in the array), but it does make the code a little less pretty: jsperf.com/anagram-algorithms/7
|
|
| Aug 10, 2015 at 3:52 | comment | added | rrowland | All good points @JcT, I've updated the answer. | |
| Aug 10, 2015 at 3:52 | history | edited | rrowland | CC BY-SA 3.0 |
deleted 42 characters in body
|
| Aug 10, 2015 at 1:24 | comment | added | JcT |
Any thoughts as to whether you could also get away with typeof word1 !== "string" || typeof word2 !== "string" in the guard at the top of the function? Guarantees we're not receiving an Array; one empty string will fail the length check, two will pass on through as anagrams. I suppose "" is in fact an anagram of ""!
|
|
| Aug 10, 2015 at 1:08 | comment | added | JcT | One other consideration - the regex we're using to strip spaces doesn't necessarily guarantee we only have alphas left; but our expectation of having a 26-value array assumes we are; I'd think there'd be some potential issues there. | |
| Aug 10, 2015 at 1:05 | comment | added | JcT |
Ah, but we know they're both the same length - so we'll either have exactly the same letters in the second string, or we'll have a letter in it that we don't have in the first. The first word having more of something means it will also have less of something else, since both words have the same available space. So say we had abb and abc (where the first has more 'b's than the first); in the second loop, we'll fail when we try to subtract from c, yes? If we survive the second loop, it means we had the same lengths and the second word didn't have any chars that weren't in the first.
|
|
| Aug 10, 2015 at 0:11 | comment | added | rrowland |
@JcT The .every loop is still catching instances where the first word has more of a certain letter than the second. The conditional is only catching instances where the second word has more of a certain letter than the first.
|
|
| Aug 9, 2015 at 23:59 | comment | added | JcT |
Just a thought - now that the conditional is in there, you may not even need that last .every loop. Anything I'm missing in thinking you can just return true?
|
|
| Aug 8, 2015 at 19:48 | comment | added | Winston Ewert | @Aron, HashMap aren't implemented using heaps, you have no idea what you are talking about. See for example the wikipedia article which describes the array of buckets, and never mentions heaps. The fact is, using a heap to implement a hash map is utterly nonsensical. | |
| Aug 7, 2015 at 18:21 | comment | added | Simon Kuang | I think my solution might be a little bit faster. | |
| Aug 7, 2015 at 15:19 | comment | added | rrowland | @JcT Great observation! I've added a conditional. | |
| Aug 7, 2015 at 15:18 | history | edited | rrowland | CC BY-SA 3.0 |
added 31 characters in body
|
| Aug 7, 2015 at 14:51 | comment | added | JcT |
You may be able to return false from that second loop a bit earlier (before attempting to subtract) if !counts[index].
|
|
| Aug 7, 2015 at 9:25 | comment | added | Ismael Miguel |
if (!word1 || !word2 || !word1.length || !word2.length) will fail if I pass an array or an array-like object.
|
|
| Aug 7, 2015 at 8:48 | history | migrated | from stackoverflow.com (revisions) | ||
| Aug 7, 2015 at 7:14 | comment | added | rrowland | Check out the speed delta! jsperf.com/anagram-algorithms | |
| Aug 7, 2015 at 7:12 | comment | added | rrowland | @Aron You made a good point about insertion speed. I sped up the algorithm by converting the lowercase characters to values 0-25 so they can quickly be looked up in by array index rather than by hash key. | |
| Aug 7, 2015 at 7:02 | comment | added | Aron | @Bergi As you fill in the Bucket Heap, it tends to an array. | |
| Aug 7, 2015 at 7:01 | comment | added | rrowland | @jpmc26 You're right, it was broken. But, the problem was I forgot to initialize the letters in the hash as Numbers. So I was trying to ++ on undefined and they all became NaN which made them equal. The updated code is working again. | |
| Aug 7, 2015 at 6:58 | comment | added | Bergi |
@Aron: What do you mean by "at the size we are working in"? If we put a bound on input size (word length), we get O(1), and if we put a bound on the number of characters we get O(n) (linear to input size).
|
|
| Aug 7, 2015 at 6:57 | comment | added | jpmc26 | @Bergi Whoops. I misdiagnosed the cause. Thanks. =) | |
| Aug 7, 2015 at 6:54 | comment | added | Aron | @Bergi no I am not. At the size we are working in, it is n log n. The log n part however is bounded... | |
| Aug 7, 2015 at 6:53 | comment | added | Bergi | @Aron: I think you're confusing a heap with the heap. Yes, initialising the map with the 26 expected letters might improve the performance, but that's really not needed as JS objects dynamically resize their maps. | |
| Aug 7, 2015 at 6:48 | comment | added | Bergi |
@jpmc26 has a point here. You forgot to initialise your properties, and they all are becoming NaN (which is falsy in the end, you might better have used an explicit == 0).
|
|
| Aug 7, 2015 at 6:48 | comment | added | Aron | @Bergi The buckets are typically stored in a Heap. You could create an implementation based on an constant sized array (which would need to be the size of 2^(size of the hash). But that is typically quite memory inefficient. In this case, we KNOW that there are only 26 different chars (excluding accents (yes english HAS accents you naïve fool)) and you can base an algorithm on an array sized 26, but it wouldn't be a generic HashMap. In fact it would not be a HashMap, since the identity function can hardly be called a Hash function. | |
| Aug 7, 2015 at 6:44 | comment | added | Bergi | @Aron: Some indexed constant access structue, call it array of buffer or whatever. | |
| Aug 7, 2015 at 6:43 | comment | added | Aron | @Bergi Where are the buckets stored? | |
| Aug 7, 2015 at 6:42 | comment | added | jpmc26 |
This function is broken. isAnagram('abccd', 'abcdd') gives back true. You need to make sure the count of each letter is the same in both hashes, not just that they have the same set of distinct letters.
|
|
| Aug 7, 2015 at 6:41 | comment | added | Bergi |
@Aron: Where did you get that from? A HashMap is implemented using hashing, with amortised O(1) access. No heapsort going on.
|
|
| Aug 7, 2015 at 6:37 | comment | added | Aron | -1 Because a HashMap is typically implemented as a Heap, which is O(log n) for inserting. More to the point. You are in effect doing the equivilent of an Insert Sort on a Heap, which "dun dun dun" is O(n log n). | |
| Aug 7, 2015 at 6:04 | comment | added | Bergi |
You should consider using every instead of reduce.
|
|
| Aug 7, 2015 at 5:08 | comment | added | rrowland | @EasyBB Yeah I wasn't aware for..in was that much slower. A quick Google search enlightened me. Thanks! | |
| Aug 7, 2015 at 4:53 | comment | added | Tushar |
@rrowland Anyway !word1 || !word2 || !word1.length || !word2.length is redundant. You can remove one of them.
|
|
| Aug 7, 2015 at 4:50 | comment | added | rrowland |
@Tushar +1 on removing trim and using \s. 0 is not a string. "0" is truthy.
|
|
| Aug 7, 2015 at 4:48 | comment | added | Tushar |
@rrowland Also remove !word1 || !word2 || . Will not work if I passed 0 as one of the string
|
|
| Aug 7, 2015 at 4:45 | comment | added | Tushar |
@rrowland You can remove trim() from word1.trim().replace(/ /g, ''); As replace is removing spaces. Also, use \s+ instead of space ` ` in regex
|
|
| Aug 7, 2015 at 4:27 | comment | added | Tushar |
@ItaloAyres See Anagram Wiki. Notice William Shakespeare = I am a weakish speller. This answer will state that these are not Anagrams
|
|
| Aug 7, 2015 at 4:27 | comment | added | Italo Ayres | @rrowland I just mentally jumped the use of sort() method. Thanks! And about the "which is the fastest" discussion, I prefer solving it the easy way: testing it! haha. | |
| Aug 7, 2015 at 4:23 | comment | added | rrowland | @ItaloAyres Both other solutions are sorting the letters of the word alphabetically and comparing. That will check for anagrams. The difference between our approaches is the computational complexity of the algorithms. | |
| Aug 7, 2015 at 4:19 | comment | added | Italo Ayres | I don't get it. The OP and @Tushar solution only check if the word is a palindrome, am I wrong? I so, this is the only correct solution by now, because checks anagrams. | |
| Aug 7, 2015 at 4:17 | comment | added | rrowland | @Tushar If you're interested in learning a little about computational complexity: en.wikipedia.org/wiki/Big_O_notation | |
| Aug 7, 2015 at 4:13 | comment | added | rrowland | Yes. 3n is an order of magnitude faster than n log n. | |
| Aug 7, 2015 at 3:50 | history | answered | rrowland | CC BY-SA 3.0 |