Given some text and a bunch of words, find where each of the words appear in the text. Text may contain spaces, words may not.
For every given word you need to return a list of (zero-based) indices of where that word starts in the text. If a word isn’t found in the text, return [-1] for that word.
text = “you are very very smart”
words = [“you”, “are”, “very”, “handsome”]
[ , , [8, 13], [-1] ]
“you” is found in the given text starting at the index 0.
“are” is found in the given text starting at the index 4.
“very” is found in the given text two times, starting at the indices 8 and 13.
“handsome” isn’t found in the given text.
Function has two arguments: string text and list of strings words.
Output: Function must return a list of lists of integers. One list for each one of the words. i-th list must contain all indices of characters in text where i-th word starts, in the ascending order. If i-th word isn’t found in the text at all, then i-th list must be [-1].
• Text and words may contain a-z, A-Z, 0-9, “$”, “#”, “@”, “?”, “;”.
• Text may contain spaces, too, but never two or more spaces consecutively. Spaces separate words in the text string.
• Text won’t start or end with a space.
• Indexing of characters in text is zero-based.
• Words list will contain unique strings.
• 1 <= number of characters in text <= 1000000
• 1 <= number of words <= 100000
• 1 <= length of any word in words or in text <= 10
We provided three solutions.
We literally compare each word from words with every word from the text. When the two are equal we take note of the start index of the word in the text.
Let n be the number of words in text,
w be the number of words and
l be the maximum length of a word.
Processing each pair of words takes O(l) time as we compare them character by character. We compare each of n words with every one of w words for the total time complexity of O(n*w*l).
The list of lists that we return takes O(w+n) space. Since words are unique, any given word from text can match at most one word from words so the total number of indexes in the returned list of lists won’t exceed n and we know that the outer list has exactly w lists, giving us a total of O(w + n).
Adding up O(w*l) of words, O(n*l) of text and O(w+n) of the auxiliary space we get O((n+w)*l).
In this solution we preprocess text and create its index, see “HashMap textIndex” variable. By the time that’d done, each word from the text has the list of its starting indices pre-compiled. All that’s left is to look up those lists of indexes for every word from words.
It takes O(I) time to calculate hashcode or to compare two strings up to l characters long. Thus populating the hashmap with n words will take O(n*l), making w searches in that hashmap will take O(w*l). Total time is the sum of those: O(n*l) + O(w*l) = O((n+w)*l)
Hashmap which we pre-compute takes O(n*l) space.
The list of lists that we return takes O(w+n) space (see explanation in Auxiliary space section for brute_force_solution.java). Summing up the two gives O(n*l) + O(w+n) = O((n*l)+w).
Text input takes O(n*l) and words take O(w*l). Adding up those two and the auxiliary space we get the total space complexity: O(n*l) + O(w*l) + O((n*l)+w) = O((n+w)*l).
In this solution we use a trie (prefix tree), First we insert all words from the text into the trie. Then we look up every word from words in the trie.
Although this solution has the same worst case time and space complexity as the hashmap based optimal_solution1.java, it will utilize less space when many words share common prefixes.
In the actual interview many interviewers will prefer to hear the trie based solution to the hashmap based one.
Insert and search operations in the trie take O(l) time each.
The algorithm makes n insertions and w searches.
O(n*l + w).
Trie takes O(n*l) space and the list of lists that we return takes O(w+n) (see explanation in Auxiliary space section for brute_force_solution.java). Adding that up we get O(n*l + w).
Text input takes O(n*l) and words take O(w*l). Adding auxiliary space to that we get the total space complexity: O(n*l) + O(w*l) + O(n*l + w) = O((n+w)*l).