【求知=>算法】最长公共前缀

发布时间:2022-01-15编辑:RainNight阅读(526)

    最长公共前缀


    编写一个函数来查找字符串数组中的最长公共前缀。

    如果不存在公共前缀,返回空字符串

    示例 1:

    输入:strs = [“flower”,”flow”,”flight”]

    输出:”fl”

    示例 2: > 输入:strs = [“dog”,”racecar”,”car”]

    输出:””

    解释:输入不存在公共前缀。

    提示: * 1 <= strs.length <= 200 * 0 <= strs[I].length <= 200 * strs[i] 仅由小写英文字母组成

    解题思路


    1. 计数统计的方式
    2. 定义集合strs,并赋值为strs = [flower, flow, flight];
    3. 定义pre,获取第一个字符串作为比对串pre = strs[0];
    4. 定义strs,获取剩下的集合;
    5. 通过strs的长度进行循环;
    6. 定义count,并赋值为count = 0;
    7. 如果当前值的长度大于pre的长度,length等于pre的总长度,否则,length等于当前值的长度;
    8. 循环length的长度,如果strs的当前值等于pre的当前值,将count加一,否则break;
    9. 将pre赋值为pre = pre[:count];
    10. 最后返回pre。

      if len(strs) == 0:
      return ""
      pre = strs[0]
      strs = strs[1:]
      
      for i in range(len(strs)):
      count = 0
      if len(pre) < len(strs[i]):
          length = len(pre)
      else:
          length = len(strs[i])
      
      for j in range(length):
          if strs[i][j] == pre[j]:
              count += 1
          else:
              break
      pre = pre[:count]
      
      return pre
      
    11. 数组切片

    • 定义集合strs,并赋值为strs = [flower, flow, flight];
    • 如果strs为空,返回空;
    • 定义n,赋值为n = 0;
    • strs的第一字符串的长度大于n;
    • 将start,赋值为start = strs[0][:n+1];
    • 循环strs,判断start字符串是否以制定的字符串输出,如果没有返回没有输出的数组;
    • n加一,返回strs。

      if not strs:
      return ''
      n = 0
      while n<len(strs[0]):
      start = strs[0][:n+1]
      for i in strs:
          if not i.startswith(start):
              return strs[0][:n]
      n +=1
      return strs[0][:n]
      
    1. 通过函数set的方式
    • 定义集合strs,并赋值为strs = [flower, flow, flight];
    • 如果strs为空,返回空;
    • 定义pre,定赋值为prev = ;
    • 定义m,每个字符串的最小值,m = min([len(s) for s in strs]);
    • 循环m,判断每个的长度是否等于1,如果是获取当前字符串集,并加上道prev上,否则break;
    • 返回prev。

      if not strs:
      return ''
      prev = ''
      m = min([len(s) for s in strs])
      for j in range(m):
      if len(set([s[j] for s in strs])) == 1:
          prev += strs[0][j]
      else:
          break
      return prev
      

    知识扩展


    startswith()方法的使用

关键字求知=>算法

Collect from 雨夜的博客 雨夜的博客