题解 | 最长公共前缀

1、解题思路

1. 特殊情况处理： 如果数组为空，直接返回空字符串。如果数组只有一个字符串，直接返回该字符串本身。
2. 初始化公共前缀： 假设第一个字符串为初始公共前缀。
3. 遍历比较： 逐个字符与公共前缀比较，逐步缩短公共前缀的长度，直到找到所有字符串共有的前缀。
4. 返回结果： 最终得到的公共前缀即为答案。

2、代码实现

C++

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param strs string字符串vector
     * @return string字符串
     */
    string longestCommonPrefix(vector<string>& strs) {
        // write code here
        if (strs.empty()) {
            return "";  // 空数组直接返回
        }
        string prefix = strs[0];    // 初始公共前缀为第一个字符串
        for (int i = 1; i < strs.size(); ++i) {
            while (strs[i].find(prefix) != 0) { // 当前字符串不包含当前前缀
                prefix = prefix.substr(0, prefix.length() - 1); // 缩短前缀
                if (prefix.empty()) return ""; // 前缀为空则返回
            }
        }
        return prefix;
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param strs string字符串一维数组 
     * @return string字符串
     */
    public String longestCommonPrefix (String[] strs) {
        // write code here
        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;
    }
}

Python

if not strs: return "" # 空数组直接返回
        prefix = strs[0] # 初始公共前缀为第一个字符串
        for s in strs[1:]: # 遍历所有字符串
            while not s.startswith(prefix): # 当前字符串不包含当前前缀
                prefix = prefix[:-1] # 缩短前缀
                if not prefix: return "" # 前缀为空则返回
        return prefix

3、复杂度分析

• 时间复杂度：O(n * m)，其中 n 是字符串数组的长度，m 是最短字符串的长度。在最坏情况下，所有字符串都需要比较到最短字符串的长度。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。