I was thinking about the problem I got at one of my exams at my university

Given a set of N words and M queries ( word s and number q) . To each query, my program should print YES if it is possible to form a word that is present in a set. I am allowed to add max q letters to given word s, but I can't change letter orders.

For example Given set S = { aataaf, cdef, bbb } and queries

aaaa 2 => YES, because I added t and f

fcd 1 => NO

I solved this using prefix tree, but is there a better way to solve this ? Complexity of prefix tree might be exponential or I implemented it in a wrong way. During my exam I was allowed to write brute force, but I found it interesting and that is why I am asking you for help