leetcode-每日一题1408. 数组中的字符串匹配(暴力枚举)和Golang里关于Index方法和Contains方法区别

简介: 题目要求我们找到字符串数组中存在字符串是其他单词的子字符串,看到题目给我们的n的范围是[1,100],所以我们可以通过暴力枚举用两个for循环一层指子串一层指找存在这个子串的单词,找到则找下个一个子串

6ba3462d6b0e437fbc6d892b762d507e.png


题目链接: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的源码看看


671a8b8aa02c43919257f73eb6e2c7bf.png


复杂度分析


  • 时间复杂度: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
}

55c81396c8d64b86936dcd1002de947a.png


复杂度分析


  • 时间复杂度:O(n logn + n2),其中n表示字符串数组的长度,对字符串数组排序需要O(n logn)的时间,查找子串需要O(n2)的时间


  • 空间复杂度:O(1),不需要额外申请空间
目录
相关文章
|
3月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
49 0
|
3月前
|
JavaScript
力扣3333.找到初始输入字符串Ⅱ
【10月更文挑战第9天】力扣3333.找到初始输入字符串Ⅱ
41 1
|
3月前
|
C++
Leetcode第43题(字符串相乘)
本篇介绍了一种用C++实现的字符串表示的非负整数相乘的方法,通过逆向编号字符串,将乘法运算转化为二维数组的累加过程,最后处理进位并转换为字符串结果,解决了两个大数相乘的问题。
31 9
|
3月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
27 4
|
3月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
26 0
Leetcode第三十三题(搜索旋转排序数组)
|
3月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
79 0
|
3月前
|
算法 C++
Leetcode第八题(字符串转换整数(atoi))
这篇文章介绍了LeetCode上第8题“字符串转换整数(atoi)”的解题思路和C++的实现方法,包括处理前导空格、正负号、连续数字字符以及整数溢出的情况。
24 0
|
3月前
【LeetCode 22】459.重复的子字符串
【LeetCode 22】459.重复的子字符串
33 0
|
3月前
【LeetCode 20】151.反转字符串里的单词
【LeetCode 20】151.反转字符串里的单词
26 0
|
3月前
【LeetCode 19】541.反转字符串II
【LeetCode 19】541.反转字符串II
25 0