目录
最⻓公共前缀（easy）
题目解析
讲解算法原理
编写代码
最⻓回⽂⼦串(medium)
题目解析
讲解算法原理
编写代码
最⻓公共前缀（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
编写⼀个函数来查找字符串数组中的最⻓公共前缀。
如果不存在公共前缀，返回空字符串""。
⽰例1：
输⼊：strs=["flower","flow","flight"]
输出："fl"
⽰例2：
输⼊：strs=["dog","racecar","car"]
输出：""
解释：输⼊不存在公共前缀。
提⽰：
1<=strs.length<=200
0<=strs[i].length<=200
strs[i]仅由⼩写英⽂字⺟组成
讲解算法原理
解法：
算法思路：
解法⼀（两两⽐较）：
我们可以先找出前两个的最⻓公共前缀，然后拿这个最⻓公共前缀依次与后⾯的字符串⽐较，这样就可以找出所有字符串的最⻓公共前缀。
解法⼆（统⼀⽐较）：
题⽬要求多个字符串的公共前缀，我们可以逐位⽐较这些字符串，哪⼀位出现了不同，就在哪⼀位截⽌。
编写代码
解法一代码：
c++算法代码：
class Solution
{
public:
string longestCommonPrefix(vector<string>& strs)
{
// 解法⼀：两两⽐较
string ret = strs[0];
for(int i = 1; i < strs.size(); i++)
ret = findCommon(ret, strs[i]);
return ret;
}
string findCommon(string& s1, string& s2)
{
int i = 0;
while(i < min(s1.size(), s2.size()) && s1[i] == s2[i]) i++;
return s1.substr(0, i);
}
};java算法代码：
class Solution
{
public String longestCommonPrefix(String[] strs)
{
// 解法⼀：两两⽐较
String ret = strs[0];
for(int i = 1; i < strs.length; i++)
{
ret = findCommon(strs[i], ret);
}
return ret;
}
public String findCommon(String s1, String s2)
{
int i = 0;
while(i < Math.min(s1.length(), s2.length()) && s1.charAt(i) ==
s2.charAt(i))
i++;
return s1.substring(0, i);
}
}解法二代码：
c++算法代码：
class Solution
{
public:
string longestCommonPrefix(vector<string>& strs)
{
// 解法⼆：统⼀⽐较
for(int i = 0; i < strs[0].size(); i++)
{
char tmp = strs[0][i];
for(int j = 1; j < strs.size(); j++)
if(i == strs[j].size() || tmp != strs[j][i])
return strs[0].substr(0, i);
}
return strs[0];
}
};java算法代码：
class Solution
{
public String longestCommonPrefix(String[] strs)
{
// 解法⼆：统⼀⽐较
for(int i = 0; i < strs[0].length(); i++)
{
char tmp = strs[0].charAt(i);
for(int j = 1; j < strs.length; j++)
{
if(i == strs[j].length() || strs[j].charAt(i) != tmp)
return strs[0].substring(0, i);
}
}
return strs[0];
}
}最⻓回⽂⼦串(medium)
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个字符串s，找到s中最⻓的回⽂⼦串。
如果字符串的反序与原始字符串相同，则该字符串称为回⽂字符串。
⽰例1：
输⼊：s="babad"
输出："bab"
解释："aba"同样是符合题意的答案。
⽰例2：
输⼊：s="cbbd"
输出："bb"
提⽰：
1<=s.length<=1000
s仅由数字和英⽂字⺟组成
讲解算法原理
解法（中⼼扩散）：
算法思路：
枚举每⼀个可能的⼦串⾮常费时，有没有⽐较简单⼀点的⽅法呢？
对于⼀个⼦串⽽⾔，如果它是回⽂串，并且⻓度⼤于2，那么将它⾸尾的两个字⺟去除之后，它仍然是个回⽂串。如此这样去除，⼀直除到⻓度⼩于等于2时呢？⻓度为1的，⾃⾝与⾃⾝就构成回⽂；⽽⻓度为2的，就要判断这两个字符是否相等了。
从这个性质可以反推出来，从回⽂串的中⼼开始，往左读和往右读也是⼀样的。那么，是否可以枚举回⽂串的中⼼呢？
从中⼼向两边扩展，如果两边的字⺟相同，我们就可以继续扩展；如果不同，我们就停⽌扩展。这样只需要⼀层for循环，我们就可以完成先前两层for循环的⼯作量。
编写代码
c++算法代码：
class Solution
{
public:
string longestPalindrome(string s)
{
// 中⼼扩展算法
int begin = 0, len = 0, n = s.size();
for(int i = 0; i < n; i++) // 依次枚举所有的中点
{
// 先做⼀次奇数⻓度的扩展
int left = i, right = i;
while(left >= 0 && right < n && s[left] == s[right])
{
left--;
right++;
}
if(right - left - 1 > len)
{
begin = left + 1;
len = right - left - 1;
}
// 偶数⻓度的扩展
left = i, right = i + 1;
while(left >= 0 && right < n && s[left] == s[right])
{
left--;
right++;
}
if(right - left - 1 > len)
{
begin = left + 1;
len = right - left - 1;
}
}
return s.substr(begin, len);
}
};java算法代码：
class Solution
{
public String longestPalindrome(String s)
{
int begin = 0, len = 0, n = s.length();
for(int i = 0; i < n; i++) // 固定所有的中间点
{
// 先扩展奇数⻓度的⼦串
int left = i, right = i;
while(left >= 0 && right < n && s.charAt(left) == s.charAt(right))
{
left--;
right++;
}
if(right - left - 1 > len)
{
begin = left + 1;
len = right - left - 1;
}
// 扩展偶数⻓度
left = i; right = i + 1;
while(left >= 0 && right < n && s.charAt(left) == s.charAt(right))
{
left--;
right++;
}
if(right - left - 1 > len)
{
begin = left + 1;
len = right - left - 1;
}
}
return s.substring(begin, begin + len);
}
}