LZ78 Dictionary

Problem

Parse s with the LZ78 algorithm and return the list of phrases in the order they are added. Each new phrase is the shortest prefix of the remaining string that is not already in the dictionary; if the remaining suffix is already known, it forms the final phrase. Return an empty list for the empty string.

Hint

Grow each phrase one character at a time until it is new.

Test cases

case 1

in: ["aaaa"]

expected: ["a","aa","a"]

case 2

in: ["abracadabra"]

expected: ["a","b","r","ac","ad","ab","ra"]

case 3

in: ["abcabcabc"]

expected: ["a","b","c","ab","ca","bc"]

case 4

in: [""]

expected: []

case 5

in: ["banana"]

expected: ["b","a","n","an","a"]

Starter codePython

def lz78_dictionary(s):
    # Your code here
    pass

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