【优选算法】（第三十一篇）

最⻓公共前缀（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);}
}