算法笔记：公共前缀

妖狐艹你老母 2024-03-16 21:48 46阅读 0赞

### 题目：[https://sunnywhy.com/sfbj/3/6/83![icon-default.png_t_N5K3][]https://sunnywhy.com/sfbj/3/6/83][https_sunnywhy.com_sfbj_3_6_83_icon-default.png_t_N5K3_https_sunnywhy.com_sfbj_3_6_83] ###

> 题目描述
> 
> 给定n个字符串，求它们的公共前缀。
> 
> 输入描述
> 
> 第一行为一个正整数n（2≤n≤20），表示字符串的个数。
> 
> 接下来n行，每行一个字符串（仅由大小写字母组成），每个字符串的长度不超过50。
> 
> 输出描述
> 
> 输出n个字符串的公共前缀。如果没有公共前缀，那么输出空行。

### 思路： ###

设置双重循环

##### 外循环： #####

从前往后循环每一个可以当作前缀的字母

##### 内循环： #####

将每一行字符串循环，由外层循环来确定每行字符串对于这个字母是否符合要求，如果不符合要求则直接退出，答案即为退出前上一个符合要求的字母（将每个字母与第一个字符串的字母进行对比即可）

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10;
    int n,flag;
    string s[N];
    int main()
    {
    	cin>>n;
    	int w=0x3f3f3f;
    	for(int i=0;i<n;i++)
    	{
    		cin>>s[i];
    		int len=s[i].size();
    		w=min(w,len);
    	}
    	int i=0,j=0;
    	for(i=0;i<w;i++)
    	{
    		for(j=0;j<n;j++)
    		{
    			if(s[j][i]!=s[0][i])
    			{
    				flag=1;
    				break;
    			}
    		}
    		if(flag)break;
    	}
    	if(i!=0)
    	{
    		for(int k=0;k<=i-1;k++)cout<<s[0][k];
    	}
    	else cout<<endl;
    	return 0;
    }

[icon-default.png_t_N5K3]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ee33a6d7e4014c628ad0f611c0449ef7.png
[https_sunnywhy.com_sfbj_3_6_83_icon-default.png_t_N5K3_https_sunnywhy.com_sfbj_3_6_83]: https://sunnywhy.com/sfbj/3/6/83

发表评论取消回复

表情：

评论列表（有 0 条评论，46人围观）

还没有评论，来说两句吧...

相关阅读

相关算法笔记：公共前缀

题目：[https://sunnywhy.com/sfbj/3/6/83![icon-default.png_t_N5K3][]https://sunnywhy.com/sf

妖狐艹你老母/ 2024年03月16日 21:48/ 0 赞/ 47 阅读

相关【Leetcode刷题】算法：最长公共前缀

文章目录一、题目描述二、解题思路 2.1 解法1 2.2 解法2 2.3 解法3 2.4 解法4

亦凉/ 2023年09月27日 23:38/ 0 赞/ 23 阅读

相关最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 `""`。示例 1: 输入: ["flower","flow","flight

川长思鸟来/ 2023年07月23日 07:00/ 0 赞/ 20 阅读

相关【最长公共前缀】算法优化笔记

题目：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。示例 1: 输入: ["flower","flo

不念不忘少年蓝@/ 2023年06月30日 08:38/ 0 赞/ 11 阅读

相关算法-Trie树/- 最长公共前缀

算法-Trie树/- 最长公共前缀 1 题目概述 1.1 题目出处 https://leetcode-cn.com/problems/longest-comm

深藏阁楼爱情的钟/ 2023年02月18日 01:46/ 0 赞/ 6 阅读

相关算法：最长公共前缀（longest-common-prefix）。

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 `""`。示例 > 输入: ["flower","flow","fligh

叁歲伎倆/ 2022年11月26日 11:56/ 0 赞/ 154 阅读

相关最长公共前缀

题目：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。示例 1：输入：strs = \[“flower”,“flow”

缺乏、安全感/ 2022年10月26日 12:57/ 0 赞/ 208 阅读

相关最长公共前缀

[lintcode最长公共前缀][lintcode] class Solution { public: / @pa

短命女/ 2022年09月24日 12:27/ 0 赞/ 197 阅读

相关画解算法：14. 最长公共前缀

题目链接 [leetcode-cn.com/problems/lo…][leetcode-cn.com_problems_lo] 题目描述编写一个函数来查找字符

怼烎@/ 2022年01月12日 00:55/ 0 赞/ 103 阅读

相关最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。示例 1: 输入: ["flower","flow","

- 日理万妓/ 2021年10月30日 00:46/ 0 赞/ 347 阅读