14.最长公共前缀

题目描述

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

如果不存在公共前缀，返回空字符串 ""。

示例1:

输入: ["flower","flow","flight"]
输出: "fl"

示例2:

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

思路

1.暂时先取数组中的第一个字符串为最长前缀。
2.将数组中的其他元素与最长前缀相比较，然后动态截取最长前缀，若最长前缀的长度为0，则可以直接返回空字符串。

Java代码实现

   public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0)
            return "";
        String temp = strs[0];

        for (int i = 1; i < strs.length; i++) {
            int j=0;
            for (;j<strs[i].length() && j<temp.length();j++){
                if(temp.charAt(j) != strs[i].charAt(j))
                    break;
            }
            temp = temp.substring(0,j);
            if("".equals(temp))
                return "";
        }
        return temp;
    }

Golang代码实现

func longestCommonPrefix(strs []string) string {
    if len(strs) < 1{
        return ""
    }

    res := strs[0]

    for i:=1; i<len(strs) && len(res) > 0; i++ {
        len1 := len(res)
        len2 := len(strs[i])

        cur := len1
        if len2 < len1 {
            cur = len2
        }

        j := 0
        for ;j<cur;j++ {
            if res[j] != strs[i][j]{
                break;                
            }
        }
        res = res[0:j]
    }

    return res
}