专栏首页江涛的博客leetcode - 最长公共前缀

leetcode - 最长公共前缀

题意

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

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

示例

示例 1:

输入:strs = ["flower","flow","flight"]
输出:"fl"

示例 2:

输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。

提示

  • 0 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i] 仅由小写英文字母组成

出处

链接:https://leetcode-cn.com/problems/longest-common-prefix

思路

这里我们需要拿字符串数组 strs 中的第一个字符串 str 进行遍历,然后如果说截取到的字符串 cur 满足题意就把它赋值给 res,不满足就退出循环。这里有一点就是你要单独判断数组为 0 的情况, 然后如果你是用 substr 函数截取的话,长度可以取等号的。当然你也可以不借助 JS 的一些 API,手动遍历,然后字符串相加求解。

代码

巧用 JSAPI

/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix = function (strs) {
  if (strs.length === 0) {
    return '';
  }
  let cur = '';
  let res = '';
  for (let i = 0; i <= strs[0].length; i++) {
    cur = strs[0].substr(0, i);
    if (strs.every((str) => str.startsWith(cur))) {
      res = cur;
    } else {
      break;
    }
  }
  return res;
};

export default longestCommonPrefix;

传统的解法

/**
 * @param {string[]} strs
 * @return {string}
 */
const longestCommonPrefix = function (strs) {
  let res = '';
  if (strs.length !== 0) {
    for (let i = 0; i < strs[0].length; i++) {
      if (strs.every((str) => str[i] === strs[0][i])) {
        res += strs[0][i];
      } else {
        break;
      }
    }
  }
  return res;
};

export default longestCommonPrefix;

测试

import longestCommonPrefix from '../../code/leetcode/14';

describe('test function longestCommonPrefix:', () => {
  test('test case strs = []', () => {
    const res = longestCommonPrefix([]);
    expect(res).toBe('');
  });

  test('test case strs = ["flower","flow","flight"]', () => {
    const res = longestCommonPrefix(['flower', 'flow', 'flight']);
    expect(res).toBe('fl');
  });

  test('test case strs = ["dog","racecar","car"]', () => {
    const res = longestCommonPrefix(['dog', 'racecar', 'car']);
    expect(res).toBe('');
  });

  test('test case strs = ["flower","flower","flower","flower"]', () => {
    const res = longestCommonPrefix(['flower', 'flower', 'flower', 'flower']);
    expect(res).toBe('flower');
  });

  test('test case strs = ["a"]', () => {
    const res = longestCommonPrefix(['a']);
    expect(res).toBe('a');
  });
});

说明

本文首发于 GitHub 仓库https://github.com/ataola/coding,线上阅读地址:https://zhengjiangtao.cn/coding/,转载请注明出处,谢谢!

本文分享自微信公众号 - 前端路桥(ataola),作者:丰臣正一

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-01-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode - 最长公共前缀

    LeetCode第14题,难度简单。将近两年以前做的题目了,回头看说不定会有新的做题思路。

    晓痴
  • 【LeetCode】最长公共前缀

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【一天一道Leetcode】最长公共前缀

    潘永斌
  • 【leetcode】14:最长公共前缀

    这道题还是比较简单的,不过简单的题,虽然你会做,不代表你能做的好。我觉得很多人可能会这样做:

    乔戈里
  • 【leetcode】14:最长公共前缀

    这道题还是比较简单的,不过简单的题,虽然你会做,不代表你能做的好。我觉得很多人可能会这样做:

    帅地
  • LeetCode-14 最长公共前缀

    今天我们学习第14题最长公共前缀,这是一道简单题。像这样字符串的题目经常作为面试题来考察面试者算法能力和写代码能力,因此最好能手写出该题。下面我们看看这...

    用户3470542
  • leetcode 14 | 最长公共前缀

    分析:找到数组中长度最小的元素min(从后面更快的例子来看,这个好像不需要~),然后从min的第一字符开始,去查找剩余元素是否在相同位置是同一个字符。

    ACM算法日常
  • LeetCode 14. 最长公共前缀

    freesan44
  • LeetCode PHP 最长公共前缀

    友情提示:此篇文章大约需要阅读 2分钟35秒,不足之处请多指教,感谢你的阅读。订阅本站

    Meng小羽
  • Leetcode-14. 最长公共前缀

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-common-prefix 著作权归...

    悠扬前奏
  • LeetCode 14. 最长公共前缀 - Easy

    这里首要明确,最长公共,也就是从数组中的每一个开始比对,如果出现不一样则停止比对。当初我就是这里犯了嘀咕。

    HLQ_Struggle
  • 【刷穿 LeetCode】14. 最长公共前缀(简单)

    说明:判断条件不一定要写成 i < Integer.MAX_VALUE,题目给出了范围是 200 以内,写成 i <= 200 也可以。不影响执行效率。

    宫水三叶的刷题日记
  • 【LeetCode】(No.014)最长公共前缀

    最长公共前缀指的是字符串数组中所有公共最长的前缀。 如果是空串的话,那么说明前缀就是“” 如果都是以“ ”开头的,那么就是“ ” 然后最长的前缀不会超过最短的字...

    PM小王
  • LeetCode 算法 | 最长公共前缀?

    首先,我们将描述一种查找一组字符串的最长公共前缀 LCP(S_1 \ldots S_n)LCP(S1…Sn) 的简单方法。 我们将会用到这样的结论:

    技术从心
  • LeetCode No.14 最长公共前缀

    输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。 说明:

    week
  • 力扣 (LeetCode)-14. 最长公共前缀|刷题打卡

    每天学习编程,让你离梦想更新一步,感谢不负每一份热爱编程的程序员,不论知识点多么奇葩,和我一起,让那一颗四处流荡的心定下来,一直走下去,加油,2021加油!欢迎...

    达达前端
  • [LeetCode] Longest Common Prefix 最长公共前缀 [LeetCode] Longest Common Prefix 最长公共前缀

    链接:https://leetcode.com/problems/longest-common-prefix/#/description 难度:Easy ...

    尾尾部落
  • 【leetcode刷题】T63-最长公共前缀

    木又AI帮
  • 【leetcode刷题】20T9-最长公共前缀

    https://leetcode-cn.com/problems/longest-common-prefix/

    木又AI帮

扫码关注云+社区

领取腾讯云代金券