题目链接：https://leetcode.cn/problems/string-matching-in-an-array/
思路
方法一、暴力枚举
直接想法
题目要求我们找到字符串数组中存在字符串是其他单词的子字符串，看到题目给我们的n的范围是[1，100]，所以我们可以通过暴力枚举用两个for循环一层指子串一层指找存在这个子串的单词，找到则找下个一个子串
代码示例
func stringMatching(words []string) (ans []string) { for i, x := range words{ for j, y := range words{ if i != j && strings.Contains(y, x){ //strings.Index(y, x) >= 0 ans = append(ans, x) break } } } return }
注意：Index方法和Contains方法在这里的速度和效率是一样的，Contains的源码里是直接调用的Index方法，所以二者其实本质上都是Index方法，Index方法的内部其实也是用暴力求解，但是不同的是，他有偷懒且灵巧机制，不是纯暴力求，有兴趣的可以去Index的源码看看
复杂度分析
- 时间复杂度：O(n2)，其中n表示字符串数组的长度，需要用到两个for循环
- 空间复杂度：O(1)，不需要额外申请空间
方法二、暴力枚举
直接思想
这个方法是从leetcode其他ac人看到的，本质上也是暴力枚举，但是不同的是，先把字符串数组按照长度从长到短排序，然后只需要去找后面比自己短的子串是不是包含在自己当中即可
代码示例
func stringMatching(words []string) []string { sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) }) n := len(words) var res []string for i := 0; i < n; i++ { for j := i + 1; j < n; j++ { if strings.Index(words[j], words[i]) >= 0 { res = append(res, words[i]) break } } } return res }
复杂度分析
- 时间复杂度：O(n logn + n2)，其中n表示字符串数组的长度，对字符串数组排序需要O(n logn)的时间，查找子串需要O(n2)的时间
- 空间复杂度：O(1)，不需要额外申请空间
