Timeline for Check if two strings are permutation of each other
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 17, 2016 at 7:46 | vote | accept | CodeYogi | ||
| Oct 8, 2016 at 18:45 | comment | added | Roland Illig |
@Veedrac asymptotically you may be right. I'm more concerned about practical performance though, therefore preferring \$O(n \log n)\$ with a small constant over \$O(n)\$ with a large constant. Using a HashMap looks like using a lot of heap memory during the computation.
|
|
| Oct 8, 2016 at 11:55 | comment | added | Veedrac |
@RolandIllig If dealing with arbitrary code points, just use a HashMap instead of an array. It's still asymptotically faster than sorting.
|
|
| Oct 8, 2016 at 11:53 | comment | added | Veedrac | @I'lladdcommentstomorrow That technique only really makes sense for small words; multiplication on big integers is slow and space inefficient. | |
| Oct 8, 2016 at 11:44 | comment | added | CodeYogi | Since sorting is involved therefore we have O(nlogn), I am missing something? | |
| Oct 8, 2016 at 11:28 | comment | added | I'll add comments tomorrow |
Yet another approach might be to substitute each occurrence of a character by a unique prime number, then multiply all numbers of a string. Permutations of a String will have the same result. This has other problems like possibly creating very large numbers and the substitution of characters with primes. But it avoids explicitly counting the occurrences of each character.
|
|
| Oct 8, 2016 at 10:41 | history | answered | Roland Illig | CC BY-SA 3.0 |