Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix)
If I have a set of words and need to return which of them start with a certain prefix, can that complexity be less than O(n*d), where n is the number of words and d is the prefix. I'm asking because of this video: https://www.youtube.com/watch?v=QGVCnjXmrNg (1:20 starts discussing the solution), where it says it can be lowered through using a trie with all of the words, but I think the creation of the trie would take O(n*t) complexity, where t is the average length of the words. Assume that all words will be at least as long as d (any word which has length smaller than d is disregarded immediately in the solution below, but is still considered during the creation of the trie in the video).
My idea for the solution is the simple one: go through each word and check if it starts with the same prefix. 864
If it does, add it to the list of words which start with that prefix, otherwise don't. The reason I think this is the best solution possible in terms of worst-case complexity is as follows: if we skip even one character or one string, we may return the wrong answer. This is the minimum input that is to be considered and in any other case, it is also considered (for example, in the solution that input is considered during the creation of the trie).
Example javascript code:
function solve(prefix, words) {
//startsWith has worst-case complexity O(d) where d is the length of the prefix
function startsWith(word, prefix) {
//this doesn't change worst-case complexity but means that the only disregardable input is disregarded
if (prefix.length > word.length) return false;
for (let i = 0; i < prefix.length; i++) {
if (prefix[i] !== word[i]) {
return false;
}
}
return true;
}
const wordsArray = [];
//since there are n (n is the length of the words array) and every iteration has worst-case complexity O(d),
// we have a worst-case complexity of O(n*d)
for (let i = 0; i < words.length; i++) {
if (startsWith(words[i], prefix)) {
wordsArray.push(words[i]);
}
}
return wordsArray;
}
console.log(solve("do", ["dog", "dark", "cat", "door", "dodge"]));
I'm asking that because in the video it was mentioned that it can be faster than O(n*d), but I believe the solution was wrongly analyzed. I, however, am just a hobbyist and feel like it is more likely I'm missing something here. 864