P6965 [NEERC 2016] Binary Code

Ben has recently learned about binary prefix codes. A binary code is a set of $n$ distinct nonempty code words $s_{i}$ , each consisting of 0s and $1s.$ A code is called a prefix code if for every $i ≠ j$ neither $s_{i}$ is a prefix of $s_{j}$ nor $s_{j}$ is a prefix of $s_{i}$ . A word $x$ is called a prefix of a word $w$ if there exists a possibly empty word $y$ , such that xy $= w$ . For example, $x = 11$ is a prefix of $w = 110$ and $x = 0100$ is a prefix of $w = 0100$ . Ben found a paper with $n$ lines of binary code in it. However, this paper is pretty old and there are some unreadable characters. Fortunately, each word contains at most one unreadable character. Ben wants to know whether these $n$ lines could represent a binary prefix code. In other words, can he replace every unreadable character with $0$ or $1$ , so that the code becomes a prefix code?

N/A

N/A

Time limit: 2 s, Memory limit: 2048 MB.