3 ms·
Unless you want your algorithm to produce wrong results sometimes, you have to check whether two strings are sctually equal even if you know they are really lik
by ithkuil 4y ago
Unless you want your algorithm to produce wrong results sometimes, you have to check whether two strings are sctually equal even if you know they are really likely to br equal (since they hash to the same value)
- krackers 4y agoThat's true, but practically when you do this you can just say the probability of a false positive is bounded above by 1/1e5 or so and you just ignore it, because most likely the only reason you care about the longest palindromic substring in the first place is to pass the leetcode autograder. Edit: For a more rigorous proof of the error bound, see https://baites.github.io/algorithms/algorithm-analysis/2020/03/23/string-hashing-and-palindromes.html https://baites.github.io/algorithms/algorithm-analysis/2020/... Basically it's O(n)/P where P is your prime modulus (usually 1e6 + 3 or 1e9 + 9), so for most practical input lengths your probability of collision is negligibly small enough that you'll pass the autograder).