最长公共前缀 图解题解

这道题到底在问什么

输入

strs=["interpreter", "interpreting", "interpreted", "interpretation"]

输出

"interpret"

最优解：一步一步想明白

1. 3记住这条：逐列比较所有字符串的同一位，全相同就延长，一旦某个不同或某串到头，前缀就到这停。
2. 4上面一排是第一个单词 "interpreter" 的每一位字符（下标固定）。我们以它为基准，从第 0 列开始，逐列去和其它单词的同一位比。公共前缀一开始是空的。
3. 5比较第 0 列：基准单词这一位是 'i'。右边列出每个单词在第 0 列的字符——逐个看它们是不是都等于 'i'。
4. 6第 0 列所有单词都是 'i'，全相同！把 'i' 并入公共前缀，前缀变成 "i"，这一列变绿，继续看下一列。
5. 7比较第 1 列：基准单词这一位是 'n'。右边列出每个单词在第 1 列的字符——逐个看它们是不是都等于 'n'。
6. 8第 1 列所有单词都是 'n'，全相同！把 'n' 并入公共前缀，前缀变成 "in"，这一列变绿，继续看下一列。
7. 9比较第 2 列：基准单词这一位是 't'。右边列出每个单词在第 2 列的字符——逐个看它们是不是都等于 't'。
8. 10第 2 列所有单词都是 't'，全相同！把 't' 并入公共前缀，前缀变成 "int"，这一列变绿，继续看下一列。
9. 11比较第 3 列：基准单词这一位是 'e'。右边列出每个单词在第 3 列的字符——逐个看它们是不是都等于 'e'。
10. 12第 3 列所有单词都是 'e'，全相同！把 'e' 并入公共前缀，前缀变成 "inte"，这一列变绿，继续看下一列。
11. 13比较第 4 列：基准单词这一位是 'r'。右边列出每个单词在第 4 列的字符——逐个看它们是不是都等于 'r'。
12. 14第 4 列所有单词都是 'r'，全相同！把 'r' 并入公共前缀，前缀变成 "inter"，这一列变绿，继续看下一列。
13. 15比较第 5 列：基准单词这一位是 'p'。右边列出每个单词在第 5 列的字符——逐个看它们是不是都等于 'p'。
14. 16第 5 列所有单词都是 'p'，全相同！把 'p' 并入公共前缀，前缀变成 "interp"，这一列变绿，继续看下一列。
15. 17比较第 6 列：基准单词这一位是 'r'。右边列出每个单词在第 6 列的字符——逐个看它们是不是都等于 'r'。
16. 18第 6 列所有单词都是 'r'，全相同！把 'r' 并入公共前缀，前缀变成 "interpr"，这一列变绿，继续看下一列。
17. 19比较第 7 列：基准单词这一位是 'e'。右边列出每个单词在第 7 列的字符——逐个看它们是不是都等于 'e'。
18. 20第 7 列所有单词都是 'e'，全相同！把 'e' 并入公共前缀，前缀变成 "interpre"，这一列变绿，继续看下一列。
19. 21比较第 8 列：基准单词这一位是 't'。右边列出每个单词在第 8 列的字符——逐个看它们是不是都等于 't'。
20. 22第 8 列所有单词都是 't'，全相同！把 't' 并入公共前缀，前缀变成 "interpret"，这一列变绿，继续看下一列。
21. 23比较第 9 列：基准单词这一位是 'e'。右边列出每个单词在第 9 列的字符——逐个看它们是不是都等于 'e'。
22. 24第 9 列出现不一致：单词 "interpreting" 这一位是 'i'，不等于基准的 'e'。只要有一个单词不同或到头，公共前缀就到此为止——停！最终公共前缀就是 "interpret"。
23. 25扫描结束：前 9 列（绿色）是所有单词都一致的部分，它们拼起来 "interpret" 就是最长公共前缀。后面的列因为出现了不一致，不再属于公共前缀。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

def longestCommonPrefix(strs):
    if not strs: return ""
    base = strs[0]                 # 以第一个单词为基准
    for col in range(len(base)):    # 逐列
        ch = base[col]
        for w in strs:             # 比较所有单词的同一位
            if col >= len(w) or w[col] != ch:
                return base[:col]   # 不同/到头 → 前缀到此为止
    return base                     # 基准串本身就是公共前缀

string longestCommonPrefix(vector<string>& strs){
    if(strs.empty()) return "";
    string base = strs[0];           // 基准串
    for(int col = 0; col < (int)base.size(); col++){
        char ch = base[col];
        for(auto& w : strs)          // 比较所有单词同一位
            if(col >= (int)w.size() || w[col] != ch)
                return base.substr(0, col);  // 不同/到头 → 停
    }
    return base;
}

public String longestCommonPrefix(String[] strs) {
    if (strs == null || strs.length == 0) return "";
    String base = strs[0];               // 基准串
    for (int col = 0; col < base.length(); col++) {
        char ch = base.charAt(col);
        for (String w : strs)            // 比较所有单词同一位
            if (col >= w.length() || w.charAt(col) != ch)
                return base.substring(0, col);  // 不同/到头 → 停
    }
    return base;
}

复杂度

面试官可能追问