Comment by chaoxu | Hacker News Reader

Comment by chaoxu | Hacker News Reader

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.

It 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.

Isn't that O(n∙m²)?

    for each string (n)
      for each char (n∙m)
        zero out char, compute hash (n∙m²)

If 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

Right, I meant using a polynomial hash.

Indeed, but I want an algorithm with deterministic O(nm) time.

Reply on news.ycombinator.com