LeetCode 14 Longest Common Prefix(最长公共前缀)(String)

版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/49184355

翻译

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

原文

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

注释

"abcdefg"
"abcdefghijk"
"abcdfghijk"
"abcef"

上面的字符串数组的最长公共前缀就是"abc"

分析

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

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

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

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

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

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

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

  • 如果jlen相等了,说明已经遍历完所有的字符串

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

LeetCode 14 Longest Common Prefix(最长公共前缀)(String)

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 {
                    return prefix.toString();
                }
            }
        }
        return prefix.toString();
    }
上一篇:Spring事务配置的五种方式


下一篇:LoadRunner中HTML模式与URL模式的区别