0014._longest_common_prefix.md

Links:

1. https://leetcode.com/problems/longest-common-prefix/
2. https://leetcode-cn.com/problems/longest-common-prefix/submissions/

Tags

1. 字符串

Solution1:

python标准库

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        import os
        return os.path.commonprefix(strs)

Solution 2

1. 取第一个单词 s，和后面的单词逐个找出最长前缀。

class Solution:
    def longestCommonPrefix(self, s):
        if not s:
            return ""
        res = s[0]
        i = 1
        while i < len(s):
            while s[i].find(res) != 0:  # 最长前缀总是从第一个字符开始
                res = res[0:len(res)-1] 
            i += 1
        return res

Solution 3

Solution 2有一个缺点：假如列表最后的字符串非常短，也总是会遍历完整个列表。 所以对不同字符串的相同列逐个比较。

1. 取每一个单词的同一位置(利用zip)的字母(即不同字符串相同下标的字符)，看是否相同(利用set)。

class Solution:
    def longestCommonPrefix(self, strs):
        res = []
        for tmp in zip(*strs):
            tmp_set = set(tmp)
            if len(tmp_set) == 1:
                res.append(tmp_set.pop())
            else:
                break
        res = ''.join(res)
        return res

---

class Solution:
    def longestCommonPrefix(self, strs):
        res = ''
        for tmp in zip(*strs):
            tmp_set = set(tmp)
            if len(tmp_set) == 1:
                res += tmp_set.pop()
            else:
                break
        return res

Solution4 横向比较

每次比较两个字符串，同时更新最长公共前缀。

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func lcp(str1, str2 string) string {
	length := min(len(str1), len(str2))
	index := 0

	for index < length && str1[index] == str2[index] {
		index++
	}

	return str1[:index]
}

func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}

	prefix := strs[0]
	count := len(strs)

	for i := 1; i < count; i++ {
		prefix = lcp(prefix, strs[i])
		if len(prefix) == 0 {
			break
		}
	}

	return prefix
}

Solution 5 纵向比较

func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}

	prefix := strs[0]

	for i := 0; i < len(prefix); i++ {
		for j := 1; j < len(strs); j++ {
			if i >= len(strs[j]) || strs[j][i] != strs[0][i]{
				return strs[0][:i]
			}
		}
	}

	return prefix
}