题目链接：https://leetcode.cn/problems/string-matching-in-an-array/

思路

方法一、暴力枚举

直接想法
The question asks us to find the substrings of other words that exist in the string array,See the title given to usn的范围是[1,100],So we can use two by brute force enumerationforOne layer of the loop refers to the substring and the other refers to the word that exists in the substring,If found, find the next substring

代码示例

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方法和ContainsThe method here is the same in speed and efficiency,ContainsThe source code is called directlyIndex方法,So both are essentially the sameIndex方法,IndexThe inner part of the method is actually solved by brute force,但是不同的是,He has lazy and nimble mechanics,Not pure violence,有兴趣的可以去Index的源码看看

复杂度分析

• 时间复杂度：O(n²),其中nIndicates the length of the string array,需要用到两个for循环
• 空间复杂度：O(1),不需要额外申请空间

方法二、暴力枚举

direct thought
这个方法是从leetcode其他ac人看到的,Also brute force enumeration in nature,但是不同的是,First sort the string array in descending order of length,Then you only need to find out whether the substring that is shorter than yourself is included in yourself

代码示例

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²),其中nIndicates the length of the string array,Required to sort an array of stringsO(n logn)的时间,Find substring requiredO(n²)的时间
• 空间复杂度：O(1),不需要额外申请空间