String Matching in an Array

main.md

Question

Approach

My approach begins by creating a dictionary called word_lengths to precompute the lengths of all the words in the input words list. This dictionary helps to efficiently track the length of each word and minimizes the need for recalculating word lengths during comparisons.

Next, I define a res array to store the words that meet the substring condition. Then, I iterate through the list words using a nested loop. For the outer loop, I keep track of the current word as word and its index i. For the inner loop, I go through each word again, referring to it as other_word and keeping its index as j.

Inside the nested loop, I add a check to skip comparing a word with itself by ensuring i != j. If this condition passes, I then proceed to check two things:

1. If the length of word is less than or equal to the length of other_word. This ensures that word can potentially be a substring.
2. If word is a substring of other_word. This is done using the in operator in Python.

If both conditions are satisfied, I append word to the res array and immediately break out of the inner loop since there’s no need to check further for this word.

Finally, after processing all the words, I return the res array containing all words that are substrings of another word.

Well, brute force works. Yayy!

Implementation

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        res = []
        word_lengths = {word: len(word) for word in words}

        for i, word in enumerate(words):
            for j, other_word in enumerate(words):
                if i != j:
                    if word_lengths[word] <= word_lengths[other_word] and word in other_word:
                        res.append(word)
                        break
        
        return res

Complexities

• Time: O(n^2.k), where (n) is the number of words and (k) is the average length of the words.
• Space: O(n), for the word_lengths dictionary and result list.

Another approach to consider (instead of doing brute force)

Instead of comparing every pair of words, sort the words list by the length of the strings. This allows to only compare smaller words with larger words that follow them in the sorted order. Then iterate through the sorted list and check each word against all words that are longer (since the sorted order ensures this). To avoid duplicates, store the results in a set and convert it back to a list at the end.

This time, the time complexity will be o(n^2) and space remains the same - O(n).

Implementation

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        words.sort(key=len)
        result = set()

        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if words[i] in words[j]:
                    result.add(words[i])
        
        return list(result)