Timeline for Determining whether two scrambled strings are equivalent
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 21, 2014 at 16:27 | history | edited | Andrej | CC BY-SA 3.0 |
deleted 23 characters in body
|
| Nov 21, 2014 at 16:23 | comment | added | Andrej | Good point on hashmap amortized constant time @skeggse | |
| Nov 21, 2014 at 15:38 | comment | added | skeggse |
@Andrej HashMaps are constant-time (amortized) for puts and gets. It looks to me like this is still O(N) even in the worst case where the two strings are large, and only differ by one character. This is because the first loop would run in O(N) time, and the second loop would run in up to O(N) time, which is simply O(N) total.
|
|
| Nov 21, 2014 at 6:36 | comment | added | Andrej | @LukeWillis this is due to using the Map. Originally it was a for loop only with O(N). | |
| Nov 20, 2014 at 17:27 | comment | added | Luke Willis |
Also you can use foreach instead of setting up your own iterator if you like.
|
|
| Nov 20, 2014 at 17:24 | comment | added | Luke Willis | This looks suspiciously like O(n) to me... How'd you get O(n log n)? | |
| Nov 20, 2014 at 2:42 | comment | added | Andrej | Added a map to account for same length strings with same checksum. Thanks @Robby Cornelissen for the counter example that exposed the issue. | |
| Nov 20, 2014 at 2:40 | history | edited | Andrej | CC BY-SA 3.0 |
Added map that fixes a new test case; added two comments
|
| Nov 20, 2014 at 2:38 | history | undeleted | Andrej | ||
| Nov 20, 2014 at 2:23 | history | deleted | Andrej | via Vote | |
| Nov 20, 2014 at 2:23 | comment | added | Andrej | Correct. The check sum approach fails in this case. | |
| Nov 20, 2014 at 2:19 | comment | added | Robby Cornelissen |
That doesn't look right. assertTrue(HelloWorld.same("abd", "bcb")); will succeed while it should not.
|
|
| Nov 20, 2014 at 2:13 | history | answered | Andrej | CC BY-SA 3.0 |