MediumNLPnlp-296

Constrained Trie Remaining Depth

Problem

Report how deep a constrained decoding trie still descends below a prefix. words is the list of allowed complete strings and prefix is the already-generated text.

Return the maximum number of additional characters needed to finish any allowed word that starts with prefix, 0 when prefix is already a complete allowed word and cannot be extended, and -1 when prefix is not a prefix of any allowed word.

Hint

Filter words that start with the prefix and take the largest remaining length.

Test cases

case 1

in: [["cat","car","dog"],"ca"]

expected: 1

case 2

in: [["cat","catalog"],"cat"]

expected: 4

case 3

in: [["cat"],"cats"]

expected: -1

case 4

in: [[],"ab"]

expected: -1

case 5

in: [["a"],""]

expected: 1

Starter codePython

def constrained_trie_remaining_depth(words, prefix):
    # Your code here
    pass

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