14. Longest Common Prefix(Easy)

题目描述

原题

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

If there is no common prefix, return an empty string “”.

Example 1:

Input: [“flower”,”flow”,”flight”]
Output: “fl”

Example 2:

Input: [“dog”,”racecar”,”car”]
Output: “”
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

原题翻译

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

如果没有公共前缀，则返回空字符串””。

例1:

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

例2:

输入: [“dog”,”racecar”,”car”]
输出: “”
解释: 输入字符串中没有公共前缀。

注意:

所有给定的输入都是小写字母a-z。

解法一(Mine)

主要思想

按每位依次比对字符串数组中的每个字符。
注意：若遍历到某个字符串的第i个字符，其为当前字符串的最后一位，后面的字符就无需比对了。

运行速度：超过了74.19%的解答。

内存使用：超过了100%的解答。

源码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0)
            return "";
        else if (strs.length == 1)
            return strs[0];
        StringBuilder res = new StringBuilder();
        int index = 0;
        char temp = ' ';
        boolean flag = true;
        f1: while (flag) {
            f2: for (int i = 0; i < strs.length; i++) {
                if ("".equals(strs[i]))
                    break f1;
                if (i == 0)
                    temp = strs[i].charAt(index);
                else if (temp != strs[i].charAt(index))
                    break f1;
                else if (i == strs.length - 1)
                    if (temp == strs[i].charAt(index))
                        res.append(temp);
                if (index >= strs[i].length() - 1)
                    flag = false;
            }
            index++;
        }
        return res.toString();
    }
}

解法二

主要思想

比较前两个字符串，得到公共前缀，与第三个字符串比较，直至公共前缀为空。

运行速度：超过了100%的解答。

内存使用：超过了80.70%的解答。

源码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) 
            return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++)
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }        
        return prefix;
    }
}

解法三

主要思想

与我的解法思想相同。

想象一下，一个非常短的字符串位于数组的末尾。上述方法仍将非常困难。优化此情况的一种方法是进行垂直扫描。在转到下一列之前，我们在同一列（字符串的相同字符索引）上从上到下比较字符。

运行速度：超过了74.19%的解答。

内存使用：超过了100%的解答。

源码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) 
            return "";
        for (int i = 0; i < strs[0].length() ; i++){
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j ++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c)
                    return strs[0].substring(0, i);             
            }
        }
        return strs[0];
    }
}

解法四

主要思想

分治。先求左半边，再求右半边，然后合并。

运行速度：超过了74.19%的解答。

内存使用：超过了100%的解答。

源码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";    
            return longestCommonPrefix(strs, 0 , strs.length - 1);
    }

    private String longestCommonPrefix(String[] strs, int l, int r) {
        if (l == r) {
            return strs[l];
        }
        else {
            int mid = (l + r)/2;
            String lcpLeft =   longestCommonPrefix(strs, l , mid);
            String lcpRight =  longestCommonPrefix(strs, mid + 1,r);
            return commonPrefix(lcpLeft, lcpRight);
       }
    }

    String commonPrefix(String left,String right) {
        int min = Math.min(left.length(), right.length());       
        for (int i = 0; i < min; i++) {
            if ( left.charAt(i) != right.charAt(i) )
                return left.substring(0, i);
        }
        return left.substring(0, min);
    }
}

解法五

主要思想

二分法。把第一个字符串分成两半，判断前一半是不是公共前缀。若是，后一半分成两半；若不是，前一半分成两半。

运行速度：超过了100%的解答。

内存使用：超过了97.08%的解答。

源码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0)
            return "";
        int minLen = Integer.MAX_VALUE;
        for (String str : strs)
            minLen = Math.min(minLen, str.length());
        int low = 1;
        int high = minLen;
        while (low <= high) {
            int middle = (low + high) / 2;
            if (isCommonPrefix(strs, middle))
                low = middle + 1;
            else
                high = middle - 1;
        }
        return strs[0].substring(0, (low + high) / 2);
    }

    private boolean isCommonPrefix(String[] strs, int len){
        String str1 = strs[0].substring(0,len);
        for (int i = 1; i < strs.length; i++)
            if (!strs[i].startsWith(str1))
                return false;
        return true;
    }
}