Today’s problem

https://leetcode.com/problems/string-matching-in-an-array/description/

Intuition

Do what the question ask.

Approach

First sort the words by its length, then iterate all string that has a larger string length. If the current string is a substring of the new string, then put it into the answer list.

Actually you do not need to sort the array, but the sort would accelerate the process.

Complexity

• Time complexity: $O(N^2\times L)$, N is the length of the word list, L is the length of the word.

• Space complexity: $O(N)$, because we need to store the answer.

Code

class Solution:
    def stringMatching(self, words: List[str]) -> List[str]:
        ans = []
        words.sort(key = lambda x: len(x))
        # This lambda is very import in python
        for i in range(len(words)):
            for j in range(i + 1, len(words)):
                if words[i] in words[j]:
                    ans.append(words[i])
                    break
        return ans