We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Though I'm not an expert in On calculations, I don't this it's up to an O(N^3). Undoubtedly my code can probably be optimized a bit more, but I dare say that since I DON'T compare all O(N^2) substrings and actually don't test the ones I know will produce anagrams, code running should on average be a lot lower than O(N^3). Maybe a worst case scenario might be such but definitely not an average one such as in the tests.
I do a lot of culling pre-calculation and minimize the amount of substrings to test.
1st I eliminate all unnecessary weeds (sequences of characters which don't repeat) replacing them with a single char.
2nd I build pair sets of the same char (call it A) (one pair for AA, 3 pairs for AAA, 6 pairs for AAAA, etc.)
with A (x is an arbitrary qty of other chars):
* AxA automatically has pair A,A
* AxA automatically has Ax, xA
(no anagram checking in either case)
Only then, taking AxxxxAyyyy (and 1st substring ALWAYS starting with the 1st A AND ALSO x is more than 1 char between A's, AND ALSO skip the above "automatic" anagram Axxx, xxxxA) will I:
* search for anagramatic substrings within xxxxAyyyy which match against Axxxx but: DON'T include another "A", and are shorter than the length of Axxxx. Also watch out for falling off the end of the string.
This thins out a lot of unnecessary anagram checks. I don't have the test sets (and I'm not going to resign 5 hackos for each) to see how many times I actually do an anagram check.
Using C++ (I imagine from your profile you're more java oriented so times are not really comparable) the running times for my solution are:
Sherlock and Anagrams
You are viewing a single comment's thread. Return to all comments →
Though I'm not an expert in On calculations, I don't this it's up to an O(N^3). Undoubtedly my code can probably be optimized a bit more, but I dare say that since I DON'T compare all O(N^2) substrings and actually don't test the ones I know will produce anagrams, code running should on average be a lot lower than O(N^3). Maybe a worst case scenario might be such but definitely not an average one such as in the tests.
I do a lot of culling pre-calculation and minimize the amount of substrings to test.
1st I eliminate all unnecessary weeds (sequences of characters which don't repeat) replacing them with a single char. 2nd I build pair sets of the same char (call it A) (one pair for AA, 3 pairs for AAA, 6 pairs for AAAA, etc.)
with A (x is an arbitrary qty of other chars): * AxA automatically has pair A,A * AxA automatically has Ax, xA (no anagram checking in either case)
Only then, taking AxxxxAyyyy (and 1st substring ALWAYS starting with the 1st A AND ALSO x is more than 1 char between A's, AND ALSO skip the above "automatic" anagram Axxx, xxxxA) will I: * search for anagramatic substrings within xxxxAyyyy which match against Axxxx but: DON'T include another "A", and are shorter than the length of Axxxx. Also watch out for falling off the end of the string.
This thins out a lot of unnecessary anagram checks. I don't have the test sets (and I'm not going to resign 5 hackos for each) to see how many times I actually do an anagram check.
Using C++ (I imagine from your profile you're more java oriented so times are not really comparable) the running times for my solution are:
Test Case 0 & 1: 0s
Test Case 2: 0.02s
Test Case 3: 0.16s
Test Case 4: 0.05s
Test Case 5: 0.12s