最长公共前缀

Question

写一个函数在字符串数组中查找最长的公共前缀字符串如果没有公共前缀，return一个空字符串""。示例：输入：strs = ["flower","flow","flight"] 输出：“fl” 我是编码新手并尝试解决这个问题（来自 leetcode）。我的方法是搜索字符串之间最短的字符串，这是我的代码，我不知道我哪里做错了，似乎 while 循环根本不起作用。如果有人可以帮助我，我将不胜感激。这是我的代码：

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        string = ""
        len_st = []
        for st in strs:
            len_st.append(len(st))
        m = min(len_st)
        prefix = strs[len_st.index(m)]
        while prefix:
            for st in strs:
                if prefix in st:
                    continue
                else:
                    prefix = prefix.replace(prefix[-1], "")
                break
            return prefix
        else:
            return ""

输入：["flower","flow","flight"] 输出：“flo” 预期输出：“fl”

Answer 1

确实完全没有必要手动循环。让 Python 为您完成。

def longestCommonPrefix(self, strs: List[str]) -> str:
    assert len(strs) > 0
    prefix = min(strs,key=len)
    while not all(s.startswith(prefix) for s in strs):
        prefix = prefix[:-1]
    return prefix

这使用 min() 到 return 最短的单词（如果是的话，则为一个）并选择它作为候选前缀。然后它检查是否所有提供的单词都以前缀开头。调用 all() 将在第一次失败时终止检查。然后它再次尝试使用更短的候选前缀，直到所有单词都以此开头，或者前缀是 ''.

Answer 2

方法：

首先，我们将找到最短的字符串及其长度。
其次，我们将获取第一个字符串并匹配每个字符与其他字符串。
一遇到不合适的字符就跳出循环

代码解决方案：


    public String longestCommonPrefix(String[] strs) {
        // Longest common prefix string
        StringBuilder longestCommonPrefix = new StringBuilder();
        // Base condition
        if (strs == null || strs.length == 0) {
            return longestCommonPrefix.toString();
        }
        // Find the minimum length string from the array
        int minimumLength = strs[0].length();
        for (int i = 1; i < strs.length; i++) {
            minimumLength = Math.min(minimumLength, strs[i].length());
        }
        // Loop for the minimum length
        for (int i = 0; i < minimumLength; i++) {
            // Get the current character from first string
            char current = strs[0].charAt(i);
            // Check if this character is found in all other strings or not
            for (String str : strs) {
                if (str.charAt(i) != current) {
                    return longestCommonPrefix.toString();
                }
            }
            longestCommonPrefix.append(current);
        }
        return longestCommonPrefix.toString();
    }
}

时间复杂度： O(m*n)

Space 复杂度： O(1)

最长公共前缀

Longest Common Prefix

python

string

while-loop

longest-prefix