Timeline for Exceeded time limit on Trie search with Backtracking using Swift
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 5, 2022 at 7:10 | comment | added | Martin R |
@ShawnFrank: 1) Good question. filter is the natural way to remove the outdated entries, I don't know why that is so slow. I tried different methods, and what I showed turned out to be the fastest one. Perhaps I will investigate that further when I find the time. – 2) I do not know.
|
|
| Sep 5, 2022 at 5:27 | vote | accept | Shawn Frank | ||
| Sep 5, 2022 at 5:27 | comment | added | Shawn Frank |
Works great once I added your if (!cacheValid) { logic. If I could ask a couple of last clarifications. 1 - In the !cacheValid, I initially did cache = cache.filter { key, value in return value == true } to only keep the true values although this again runs into time limit exceeded, is there something more optimal with your solution of validating the cache with compact map? 2 - The Python solution in the video did not use any caching, do you have any idea what operations in Swift underperform that might require this additional measure ? Thanks again for your help !
|
|
| Sep 5, 2022 at 5:08 | comment | added | Martin R | @ShawnFrank: That is strange, my code passed all tests even before implementing the last two points. But I have added the final code for your convenience. | |
| Sep 5, 2022 at 5:06 | history | edited | Martin R | CC BY-SA 4.0 |
added 2362 characters in body
|
| Sep 5, 2022 at 4:29 | comment | added | Shawn Frank | It is currently failing on: leetcode.com/submissions/detail/791809726/testcase | |
| Sep 5, 2022 at 4:28 | comment | added | Shawn Frank |
Thanks for your feedback Martin. I submitted with the cached improvements, however I still get the time limit exceeded, although with a different test case so I think there is an improvement. I think I need to go further with the last 2 points. I keep the true values using filter. Regarding filtering the hash in search, can you please elaborate on when I should perform this operation? Is it when the cache does not have the result or when we are trying to add a new word to a hash or some other time ?
|
|
| Sep 4, 2022 at 20:20 | history | edited | Martin R | CC BY-SA 4.0 |
added 312 characters in body
|
| Sep 4, 2022 at 19:49 | history | answered | Martin R | CC BY-SA 4.0 |