Longest Common Prefix

Apr 26, 2016


Longest Common Prefix

题目描述

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

解法

代码如下:

public static String longestCommonPrefix( String[] strs ) {
    if( strs == null || strs.length == 0 ) return "";
    if( strs.length == 1 ) return strs[0];
    int pos = 0;
    while( true ) {
        for( int i = 1; i < strs.length; ++i )
            if( strs[i-1].length() <= pos || strs[i].length() <= pos || 
                strs[i].charAt( pos ) != strs[i-1].charAt( pos ) )
                return strs[0].substring( 0, pos );
        ++pos;
    }
}

思考过程:

从位置的角度出发, 使用一个变量记录当前最长前缀位置, 对于每一个字符串中的当前最长前缀位置进行比较, 如果出现不等或出现字符串长度不足, 那么当前位置就是结果, 否则进入下一个位置.

注意该算法必须在拥有2个及以上的字符串数组中才能使用, 所以一开始进行边界情况的处理.

时空复杂度: 时间复杂度是O( min(strs[i].length()) ), 空间复杂度是O(1)


上一篇博客:Insertion Sort List
下一篇博客:Missing Number