Pwning Passwords code-golf

Alice decided to improve the security of her website by sending first five characters of an SHA-1 hash to Bob's Leaked Password Detection Service. However, she made two mistakes that let Eve decode the passwords: sending passwords over HTTP and checking the password after each character of a password is typed. Eve asks you for help in decoding the passwords, however Eve cannot really program, so she asks for help in transcribing the algorithm to a computer program or function.

Eve eavesdropped the requests for following hashes from Alice.

516B9 379FC 19C2A 9D4E1 08506 F808E A7F93 5BAA6 

How could you decode this password? Well, you can brute-force all lowercase letters. In this case the only letter whose hash starts with 516B9 is p. The hash of letter p is 516B9783FCA517EECBD1D064DA2D165310B19759.

Knowing that the password starts with p, you can brute-force the second character. In this case, the only possible character is a. The hash of pa is 379FC0D5299A71AC0F171FBB5AFB262829B4E765

You can continue to brute-force letters one by one to figure out the password was password (5BAA61E4C9B93F3F0682250B6CF8331B7EE68FD8). Well, that was simple.

Not all passwords are that simple however. Consider the following requests:

4DC7C A84FD 467D7 BD79D 12D83 

First three characters of this password are simple: rxr (467D7856C648A79A096D339A2CE5FC929658967D).

With the fourth character it gets more complicated. BD79D matches for rxrf (BD79DEC8435B8BA509A25F419F31CC2ACDE2FF0A) and rxrp (BD79DC20901B11468F8369B5B0D15894F3D96A5E). There is an ambiguity, but as it turns out, it can be resolved by trying both ways. If you assume the password starts with rxrp there is no valid letters to continue with. However, if you assume the password starts with rxrf, then it's possible to append a, resulting in rxrfa (12D83D3A429CD7D64E9A532C05C2C00C35032A94), which is a valid solution.

All passwords will be composed entirely out of lowercase letters. You can assume all inputs have a solution and there are no inputs that could possibly resolve to multiple passwords (for instance ["4DC7C", "A84FD", "467D7", "BD79D"] is an invalid input because it can match both "rxrf" and "rxrp").

There are no case requirements on the input. Your program is allowed to assume the input is lowercase. Your program is allowed to assume the input is uppercase.

Your program's average complexity must be below O(2^N). As a general rule, this means your program must not spend over 100 years on brute-forcing a 25 characters long password.

It is allowed to use external libraries or language built-in functions for computation of SHA-1 hash.

#Example Input and Output

This is a JSON representing a list of tuples of input (list of strings) and output (a string).

[ [ [ "516B9", "379FC", "19C2A", "9D4E1", "08506", "F808E", "A7F93", "5BAA6" ], "password" ], [ [ "07C34", "593B7", "0262F", "CED65", "23612", "4EF76", "B7A87" ], "letmein" ], [ [ "84A51", "87DDA", "83F67", "E6FB0", "5157D", "82CD7", "6F655", "43426" ], "codegolf" ], [ [ "7A81A", "DB3D4", "FE05B", "E7280", "32726", "30AE9", "2C61A", "A9E46", "15D98", "F780A", "3E949", "F4BF2", "6A5C4", "C4554", "FA2EA", "48A40", "5DD7F", "5284E", "C0B8D", "20D59", "9184C", "32AD9" ], "onetwothreefourfivesix" ], [ [ "84A51", "87DDA", "26CA7", "9D925", "08A23", "BE075", "3179A", "5D904", "54C70", "47790", "5D3B5", "0E4CE", "004C7", "EC8A8", "131A6", "7F47F", "41BC6", "FCF07", "D62BD", "DD14F", "6A141", "EE184", "595F8", "9D303", "BFD36" ], "correcthorsebatterystaple" ], [ [], "" ], [ [ "4DC7C", "A84FD", "467D7", "BD79D", "12D83" ], "rxrfa" ], [ [ "4DC7C", "A84FD", "467D7", "BD79D", "7B743" ], "rxrpa" ] ]