Leetcode-Q14 最长公共前缀 Longest Common Prefix

题目

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

如果不存在公共前缀,返回空字符串 “”。

  • 示例 1:

输入: [“flower”,”flow”,”flight”]
输出: “fl”

  • 示例 2:

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

  • 说明:

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

自解

自解失败😂

思路是

  • 首先取得str[0]作为标准key
  • 0号和1号比较得出最长pr,然后用这个pr再和2号比较,然后再和3号比较…

以此一直Loop到最终(如果中途找不到就直接返回’’了)

正解

Link

Solution 2: sort the array first, then you only need to compare the first and last string in array. Time complexity is O(nlgn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public string LongestCommonPrefix2(string[] strs)
{
if (strs.Length == 0) return String.Empty;
Array.Sort(strs);

var first = strs[0];
var last = strs[strs.Length - 1];
var strbuilder = new StringBuilder();
for (int i = 0; i < first.Length; i++)
{
if (first[i] != last[i])
{
break;
}
strbuilder.Append(first[i]);
}

return strbuilder.ToString();
}

槽点

这个正解实在太厉害了. 主要是利用的Array.Sort Array.Sort默认是按字母每位的升序排序. 所以可以保证首个和末位比较即可得到答案.

坚持原创技术分享,您的支持将鼓励我继续创作!