Lempel-Ziv 78 Phrase Count

Problem

Parse a string with the LZ78 algorithm and return the number of phrases. Starting at position i, extend the current phrase until it is not already in the phrase dictionary, add that new phrase, and continue right after it. If the remaining suffix is already in the dictionary, count it as one final phrase. Return 0 for the empty string.

Hint

Each phrase is the shortest prefix of the remaining string that has not been seen before.

Test cases

case 1

in: ["aaaa"]

expected: 3

case 2

in: ["abracadabra"]

expected: 7

case 3

in: ["abcabcabc"]

expected: 6

case 4

in: ["abcdef"]

expected: 6

case 5

in: [""]

expected: 0

Starter codePython

def lz78_phrase_count(s):
    # Your code here
    pass

5 test cases · run your code against them in the editor