Longest Common Prefix
Write a function to find the longest common prefix string amongst an array of strings.
这是一次性通过的简单问题了。
要点:
1 用第一个string初始化,并初始化当前maxPre为该串长度
2 从第二个string开始比较,并记录当前maxPre的最大长度
3 循环所有vector里面的string
class Solution {
public:
string longestCommonPrefix(vector<string> &strs)
{
if (strs.empty())
{
return string();
}
int maxPre = strs[0].length();
for (int i = 1; i < strs.size(); i++)
{
countPrefix(strs[0], maxPre, strs[i]);
}
return strs[0].substr(0, maxPre);
}
void countPrefix(string &initStr, int &maxPre, string &str)
{
int i = 0;
for (; i < maxPre; i++)
{
if (i >= str.length() || initStr[i] != str[i])
{
break;
}
}
maxPre = i;
}
};
2014-1-24 update 更加简洁的程序:
string longestCommonPrefix(vector<string> &strs)
{
string rs;
if (strs.empty()) return rs;
int len = strs[0].length();
for (int i = 1; i < strs.size(); i++)
{
int j = 0;
for ( ; j<len && j<strs[i].length() && strs[i-1][j]==strs[i][j]; j++);
len = j;
}
return strs[0].substr(0,len);
}
分享到:
相关推荐
LeetCode Longest Common Prefix解决方案
js js_leetcode题解之最长公共前缀_题解
给你一个字符串 s,请你返回它的 最长快乐前缀。 如果不存在满足题意的前缀,则返回一个空字符串。 示例 1: 输入:s = level 输出:l 解释:不包括 s 自己,一共有 4 个前缀(l, le, lev, leve)和 4 个后缀(l, el...
最长公共前缀 20 Valid Parentheses 有效的括号 26 Remove Duplicates from Sorted Array 删除排序数组中的重复项 32 Longest Valid Parentheses 最长有效括号 33 Search in Rotated Sorted Array 搜索旋转排序数组 ...
leetcode中文版 LeetCode # Title Chinese Tag Solution 1 Two Sum ...最长公共前缀 string 16 3Sum Closest 最接近的三数之和 two pointers,array 21 Merge Two Sorted Lists 合并两个有序链表 lin
c语言 c语言_c语言编程基础之leetcode题解第14题最长公共前缀
c++ c++_c++编程基础之leetcode题解第14题最长公共前缀.zip
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
php php_leetcode题解之实现前缀树
LeetCode674. 最长连续递增序列674. 最长连续递增序列解题思路:记录每次递增序列的长度,max存储最大长度// 递增序列更新最大长度} else
java面试题 java面试题_leetcode题解之第14题最长公共前缀
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
B中[0,j]这个部分,肯定包含B.charAt(j)的部分,最长的公共子序列2、如果两个字符串的末尾字符刚好相等,问题就被缩小为:dp[i][j] = dp
简介:给定一个未经排序的整数数组,找到最长且连续递增的子序列,并返回该序列的长度。题解 1 - typescript编辑时间:2021.1.24执行用时:92m
题目位置题解* 思路* 1、记录当前长度和最大长度* 2、每次不符合长度的时候(也就是后面一个数字不大于前面一个数的时候)让就最大长度等于当前长度和最大长度的最
3 初始值和特殊情况由于常规情况要求$$j-1\geq i+1$$,所以字符串只有两个字母或者一个字母的情况要特殊考虑一个字母的情况,肯定是回文串:两个字母的情
1、将字母按照数量从小到大排序 2、如果连续放置了两个最多的字母,就考虑放置一个次大的字母 3、否则,能放置最大的字母,就放置最大的字母 4、其他情况,没有字母
编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串 ""。示例 1:输出: "fl"示例 2:输出: ""解释: 输入不存在公共前缀
c# c#_Leetcode面试题解之第14题最长公共前缀
python python_leetcode面试题解之第14题最长公共前缀