探秘力扣之谜:如何轻松解决最长公共前缀问题?

这篇具有很好参考价值的文章主要介绍了探秘力扣之谜:如何轻松解决最长公共前缀问题?。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

探秘力扣之谜:如何轻松解决最长公共前缀问题?

本篇博客我会讲解力扣中的“14. 最长公共前缀”这道题,这是题目链接。

先来审题:
探秘力扣之谜:如何轻松解决最长公共前缀问题?
以下是几个输出示例:
探秘力扣之谜:如何轻松解决最长公共前缀问题?
提示:
探秘力扣之谜:如何轻松解决最长公共前缀问题?
这道题的思路其实并不难,也是一些字符串的常规操作的结合。大家可以先思考一下,再来听我讲解。

思路是这样的:外层循环遍历第一个字符串的每一个字符,内层循环遍历其他字符串对应位置的字符,直到遍历到不匹配的字符,或者全部匹配。

如何遍历第一个字符串呢?常规思路是这样的:

for (char* cp = str[0]; *cp; ++cp)
{
	// ...
}

但是这么写有一个问题:你怎么知道遍历的是第一个字符串中的第几个字符?如果不知道的话,就无法匹配其他字符串相同位置的字符了。

所以,最好用下标来遍历。你可以这么写:

int len = strlen(strs[0]);
for (int i = 0; i < len; ++i)
{
	// ...
}

但这么写需要先求字符串的长度,我不太喜欢。我更喜欢这么写:

for (int i = 0; strs[0][i]; ++i)
{
	// ...
}

这种写法和第一种写法中的cp指针遍历有着异曲同工之妙,都是遍历到’\0’就停止遍历。

内层循环应该遍历每一个字符串,这就是遍历数组的常规操作。

char * longestCommonPrefix(char ** strs, int strsSize){
    // 遍历第一个字符串
    for (int i = 0; strs[0][i]; ++i)
    {
    	// 遍历字符串数组
        for (int j = 0; j < strsSize; ++j)
        {
            
        }
    }
}

下面检查每个字符串对应位置的字符是否和第一个字符串对应位置的字符相同,如果相同,就继续遍历;如果不相同,则遍历结束,返回该位置之前的前缀。当然,如果2层for循环都走完了,就说明所有的字符串都是相同的,返回第一个字符串即可。

char * longestCommonPrefix(char ** strs, int strsSize){
    // 遍历第一个字符串
    for (int i = 0; strs[0][i]; ++i)
    {
        // 遍历字符串数组
        for (int j = 0; j < strsSize; ++j)
        {
            if (strs[j][i] != strs[0][i])
            {
                // 遍历结束
                strs[0][i] = '\0';
                return strs[0];
            }
        }
    }

	// 所有字符串均相同
    return strs[0];
}

探秘力扣之谜:如何轻松解决最长公共前缀问题?
这就通过了。是不是很简单?

总结

  1. 遍历字符串,除了用cp指针遍历,还可以用下标遍历。
  2. 返回字符串前缀,可以把前缀的下一个字符改成’\0’,再返回起始地址。

感谢大家的阅读!文章来源地址https://www.toymoban.com/news/detail-434974.html

到了这里,关于探秘力扣之谜:如何轻松解决最长公共前缀问题?的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 悄悄告诉你:前端如何获取本机IP,轻松一步开启网络探秘之旅

    🐔 前期回顾 Vite+Vue3+Ts 实战本地运行GPT_彩色之外的博客-CSDN博客 本地运行 使用GPT https://blog.csdn.net/m0_57904695/article/details/131851601?spm=1001.2014.3001.5501 目录  🛹 第一种:上白度  🤖 第二种:JS获取  😷  谢谢观看 几行代码,轻松获取本机 IP 地址,究竟是怎样实现的?  控制台

    2024年02月05日
    浏览(46)
  • 最长公共子序列和最长公共子串

    最长公共子序列 题目描述 给出1,2,…, n 的两个排列P 1 和 P 2 ,求它们的最长公共子序列。 输入格式 第一行是一个数 n 。 接下来两行,每行为 n 个数,为自然数1,2,…, n 的一个排列。 输出格式 一个数,即最长公共子序列的长度。 题目分析 第一阶段定义dp数组 (1)考虑规模

    2024年02月19日
    浏览(39)
  • 【算法训练-字符串 三】最长公共子串、最长公共子序列

    废话不多说,喊一句号子鼓励自己:程序员永不失业,程序员走向架构!本篇Blog的主题是【】,使用【】这个基本的数据结构来实现,这个高频题的站点是: CodeTop ,筛选条件为: 目标公司+最近一年+出现频率排序 ,由高到低的去 牛客TOP101 去找,只有两个地方都出现过才做

    2024年02月09日
    浏览(40)
  • 最长公共子序列(详细代码 注释 分析 以及求出最长公共子序列内容方法)

    文章有些长,希望能够耐心看完,并且对你有帮助,文章是自己看了书之后,总结的,如果有什么错误的地方,欢迎指出。 一些基本的概念: 子序列: 原序列中删除若干个元素得到的序列,即原序列中可以不连续的一段 子串: 原序列中任意个连续的序列元素组成的序列,

    2023年04月15日
    浏览(51)
  • 最长重复子数组,最大子序和,最长公共子序列

    欢迎批评指正!

    2024年04月13日
    浏览(62)
  • 动态规划--最长公共子序列

    动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干个子问题﹐ 即将大规模变成小规模 ,先求解子问题,然后从这些子问题的解得到原问题的解。与分治法不同的是﹐适合于用动态规划法求解的问题,经分解得到的子问题往往不是互相独立的。 他们之间有关系

    2024年02月04日
    浏览(77)
  • leetcode14. 最长公共前缀

    题目 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀,返回空字符串 “”。 解题方法: 1.首先找到数组中长度最短的数据,与数组第一个数进行交换(公共前缀的长度肯定不会大于列表中长度最短的字符串) 2.接着 因为求最长公共前缀,将数组第

    2024年01月21日
    浏览(47)
  • 最长公共子序列

    最长公共子序列,英文缩写为LCS (Longest Common Subsequence)。其定义是,一个序列 S ,如果分别是两个或多个已知序列的子序列,且是所有符合此条件序列中最长的,则 S 称为已知序列的最长公共子序列。 子串、子序列还有公共子序列的概念(在上篇LIS中也曾涉及过) ,我们以字

    2024年02月16日
    浏览(36)
  • 最长公共子序列LCA

    题目链接:3692. 最长连续公共子序列 - AcWing题库

    2024年02月13日
    浏览(39)
  • 动态规划——最长公共子序列

    先来讲解以下什么是最长公共子序列。最长公共子序列不是最长相同字符串,有点相似但不一样,来举个简单的例子,有字符串s1=bcdea,s2=abce,最长相同字符串是bc,最大公共部分是2;而最长公共子序列则是bce,最大公共部分是3。可以看出,公共子序列不需要连续相等,有相

    2023年04月19日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包