今日题目

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

思路

按照题目要求直接模拟。

解题方法

先按字符串长度排序，然后遍历所有长度更大的字符串。如果当前字符串是较长字符串的子串，则将其加入答案列表。

实际上不需要排序，但排序可以加速运行过程。

复杂度

  • 时间复杂度：$O(N^2\times L)$，N 是单词列表的长度，L 是单词的长度。

  • 空间复杂度：$O(N)$，因为需要存储答案。

代码

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