LeetCode 14 Longest Common Prefix（最长公共前缀）（String）

LeetCode 14 Longest Common Prefix（最长公共前缀）（String）

翻译

写一个函数（或方法）来寻找一个字符串数组中的最长公共前缀。

原文

Write a function to find the longest common prefix string amongst an array of strings.

注释

"abcdefg"
"abcdefghijk"
"abcdfghijk"
"abcef"上面的字符串数组的最长公共前缀就是"abc"。

分析

如下图所示，第一步就是要找出该字符串数组中的最短字符串的长度及其序列。

第二步，用 for $for$循环从第一个字符串到最后一个字符串依次做比较，具体步骤如下：

• 外层 for $for$循环中用i表示字符串长度，从 minSize $minSize$一直可以递减到 0 $0$

• 初始result$result$即为最短字符串（通过 minIndex $minIndex$确定）的前i个字符

• 内层 for $for$循环中用 j $j$表示字符串数组中的索引，依次递增。j$j$等于 minIndex $minIndex$时不做操作（因为为同一个字符串不必比较）

• 否则通过临时字符串 temp $temp$来获取索引为j的字符的前 i $i$个字符

• 需要所有的temp$temp$都与 result $result$相等

• 如果 j $j$和len$len$相等了，说明已经遍历完所有的字符串

• 每次判断的字符串长度缩减之后都更新 result $result$

public class Solution {public string LongestCommonPrefix(string[] strs) {int len = strs.Length;if(len == 0)return "";string result = "";int minSize = 100000;int minIndex = 0;if(len == 1){result = strs[0];return result;}for(int i = 0; i < len; i++){int size = strs[i].Length;if(size < minSize){minSize = size;minIndex = i;}}for(int i = minSize; i >= 0; i--){result = strs[minIndex].Substring(0,i);int j = 0;for(; j < len; j++){if(j == minIndex)continue;string temp = strs[j].Substring(0,i);if(result != temp)break;}if(j == len)return result;}return result;      }
}

updated at 2016/09/17

其实注意到这里只是求公共前缀，前缀，而不是整个字符串数组内的公共字符串，这就容易得多了。只要将字符串排序，因为都是字母字符，所以这也能达到非常好的效果。

然后只要以此比较即可。

    public String longestCommonPrefix(String[] strs) {StringBuilder prefix = new StringBuilder();if (strs != null && strs.length > 0) {Arrays.sort(strs);char[] a = strs[0].toCharArray();char[] b = strs[strs.length - 1].toCharArray();for (int i = 0; i < a.length; i++) {if (b.length > i && b[i] == a[i]) {prefix.append(b[i]);} else {String();}}}String();}