6 ms·
A friend gave me the problem for day 2 part 2, and I found it really cute. Given a set of n strings, each of length m, find if there is a pair that differs in
by chaoxu 8y ago
A friend gave me the problem for day 2 part 2, and I found it really cute.
Given a set of n strings, each of length m, find if there is a pair that differs in exactly one position.
It was not trivial to come up with an optimal and elementary O(nm) time algorithm. (by elementary, I mean something does not need a few hours to implement).
I've seen people getting running times of the form O(n^2m), O(n(n+m)) and O(nm^2) on multiple Reddit posts, and was surprised at all kind of different approaches.
- cperciva 8y agoIt was not trivial to come up with an optimal and elementary O(nm) time algorithm. Compute the hashes of the nm strings formed by taking each of the n strings and zeroing out one of the m characters. If you get any hash collisions, compare the strings.
- ahaferburg 8y agoIsn't that O(n∙m²)? for each string (n) for each char (n∙m) zero out char, compute hash (n∙m²)
- pedrosorio 8y agoIf you hand code your own hash function you can compute hash(string with zeroed out i-th character) from hash(string) in O(1) An example of such a hash is a polynomial hash (sum c_i * p^i modulo M, with p and M prime) such as the one used to explain https://en.m.wikipedia.org/wiki/Rabin–Karp_algorithm https://en.m.wikipedia.org/wiki/Rabin–Karp_algorithm
- cperciva 8y agoRight, I meant using a polynomial hash.
- chaoxu 8y agoIndeed, but I want an algorithm with deterministic O(nm) time.