Inverse Burrows-Wheeler Transform

Problem

Reconstruct the original string from its Burrows-Wheeler transform, which ends with the sentinel dollar sign.

Repeatedly sort and prepend the transform characters n times to rebuild the rotation table, then return the row that ends with the sentinel, without the sentinel. Return the empty string for empty input.

Hint

After n rounds of stable prepending, the row ending in the sentinel is the original text.

Test cases

case 1

in: ["annb$aa"]

expected: "banana"

case 2

in: ["a$"]

expected: "a"

case 3

in: ["$"]

expected: ""

case 4

in: ["b$a"]

expected: "ab"

case 5

in: ["ipssm$pissii"]

expected: "mississippi"

Starter codePython

def inverse_bwt(t):
    # Your code here
    pass

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