Advent of code Day 2 Part 2 Complexity

Conectado — Mon, 03 Dec 2018 12:38:47 +0000

I've been trying to solve the Advent of code day 2 part 2 exercise. The 'simplest' algorithm I've come up with is the following (Pseudo-code)

i <- 0
while i <= len(file) do:
    j <- i+1
    while j <= len(file) do:
        same = sameCharacters(file[i], file[j])
        if len(file[i]) == len(file[j]) == len(same+1) then:
            return same
        j++
   i++

file contains the whole exercise input, file[i] returns line number i of the input and sameCharacters returns the common characters between two words compared position by position as per explained by the exercise.

So, if the maximum length of a word is kand the number of lines in the file is nthis solution would have complexity O(n^2*k).

I've been trying to come up with a solution with a better worst-case complexity. I've thought on making a tree out of the words in the file, so that its root would point to the first letter of each word, then each node would point to the next letter and so on, the leafs would point to the index of the corresponding word in the file, so an array like [aaa, abb, baa] would become

root
/ \
a b
/\ |
a b a
| | |
a b a
| | |
0 1 2

Creating this tree would take O(n*k) but then, although I believe that this could improve performance, one would still need to search the whole tree for each word in the worst case scenario and the complexity would stay O(n^2*k). I've not come up with anything better yet, anyone has any idea?

DEV Community: Conectado

Advent of code Day 2 Part 2 Complexity