net简单级题目分享(十八)(leetcode)|Longest Common Prefix

题意：

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

示例 2:

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

说明:

所有输入只包含小写字母 a-z 。

第一种解法：

分析或步骤：

第一步：获取数组的第一个元素first。

第二步：截取first字符串的0-1位，判断数组从第二个元素到最后一个元素是否都能匹配到截取的字符串，匹配到count就加1，如果count最后的值和数组除掉第一个元素后的长度相等，则是共有前缀。

第三步：如果第二步成功匹配上，则截取first字符串的0-2位，重复第二步的判断逻辑。

C#代码：

public class Solution {

public string LongestCommonPrefix(string[] strs) {

String result = "";

if (strs.Count() == 0)

{

return "";

}

if (strs.Count() == 1)

{

return strs[0];

}

String first = strs[0];

for (int i = 1; i <= first.Count(); i++)

{

String prefix = first.Substring(0, i);

int count = 0;

for (int j = 1; j < strs.Count(); j++)

{

if (strs[j].IndexOf(prefix) == 0)

{

count = count + 1;

}

}

if (count != 0 && count == strs.Count() - 1)

{

result = prefix;

}

}

return result;

}

}

第二种解法：

分析和步骤：

第一步：获取数组中第一个元素first。

第二步：用first和数组第二个元素匹配查找，找不到就循环将first元素从0到倒数第二位截取，直到first变为空，如果first为空则表示没有相同的前缀。

第三步：用first和数组第二个元素的共有前缀与数组第三个元素进行匹配查找，依次往后循环。

C#代码：

public class Solution {

public string LongestCommonPrefix(string[] strs) {

if (strs.Count() == 0)

{

return "";

}

String first = strs[0];

for (int i = 1; i < strs.Count(); i++)

{

while (strs[i].IndexOf(first) != 0)

{

first = first.Substring(0, first.Count() - 1);

if (string.IsNullOrEmpty(first))

{

return "";

}

}

}

return first;

}

}

第三种解法：

分析和步骤：先将原数组分为两部分，左边部分依次获取共有前缀，右边部分依次获取共有前缀，再将左右两边的前缀进行查找，最后得到所有元素共有的前缀。此方法有点绕，可以通过调试或做标记及的方式理解。

C#代码：

public class Solution {

public string LongestCommonPrefix(string[] strs) {

if (strs.Count() == 0) {

return "";

}

return partOf(strs, 0, strs.Count()-1);

}

public String partOf(String[] strs, int leftIndex, int rightIndex)

{

if (leftIndex == rightIndex)

{

return strs[leftIndex];

}

else

{

int midIndex = (leftIndex + rightIndex) / 2;

String leftStr = partOf(strs, leftIndex, midIndex);

String rightStr = partOf(strs, midIndex + 1, rightIndex);

return getResult(leftStr, rightStr);

}

}

public String getResult(String leftStr, String rightStr)

{

int min = Math.Min(leftStr.Count(), rightStr.Count());

for (int i = 0; i < min; i++)

{

if (leftStr[i] != rightStr[i])

{

return leftStr.Substring(0, i);

}

}

return leftStr.Substring(0, min);

}

}

此题解法远不止上面这三种，今天这题要解出来不难，难的是这是否是当前的唯一解？是否还可以另寻他法？如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！