14.最长公共前缀.md

14. 最长公共前缀

url

题目

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

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

输入：strs = ["flower","flow","flight"]
输出："fl"

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

方法

看到这道题，找到几个字符串公共前缀，比如 strs = ["flower","flow","flight"]

• 我们肯定一眼就能找到fl是公共前缀
• 假设我们取第一个字符串，flower，分别和flow与flight去对比
• 对比啥呢，对比其他字符串是否包含flower，如果包含，则是公共前缀，如果不是呢？那就截取掉最后一个字符，即flowe，再分别和flow与flight去对比
• 以此类推，打截取到flow的时候，flow字符串正好与该字符串相等，但和flight不匹配，那么继续截取，然后从flight所在的索引循环
• 直到fl符合所有要求

code

js

let longestCommonPrefix = function(strs) {
    if (strs.length === 0)
        return "";
    let str = strs[0]
    for (let i = 1; i < strs.length; i++) {
        while(strs[i].indexOf(str) !== 0) {
            str = str.substring(0, str.length - 1);
        }
    }
    return str;
};

go

func longestCommonPrefix(strs []string) string {
	if strs == nil || len(strs) == 0 {
		return ""
	}
	str := strs[0]
	for _, v := range strs[1:] {
		for strings.Index(v, str) != 0 {
			str = str[0:len(str) - 1]
		}
	}
	return str
}

java

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