题目链接：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(n²)，其中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 + n²)，其中n表示字符串数组的长度，对字符串数组排序需要O(n logn)的时间，查找子串需要O(n²)的时间
• 空间复杂度：O(1)，不需要额外申请空间