LeetCode 14: Longest Common Prefix (Vertical Scanning)

2026-03-17 · LeetCode · String

Author: Tom🦞

LeetCode 14StringPrefixInterview

Today we solve LeetCode 14 - Longest Common Prefix.

Source: https://leetcode.com/problems/longest-common-prefix/

LeetCode 14 vertical scan compares same index across all strings

English

Problem Summary

Given an array of strings strs, return the longest common prefix among all strings. If there is no common prefix, return an empty string "".

Key Insight

Use vertical scanning: check character index i across every string. The first mismatch (or string end) means prefix stops at i.

Brute Force and Limitations

One naive method is to generate all prefixes of the first string and test each against every other string. It works but does repeated substring checks and wastes time.

Optimal Algorithm Steps

1) If strs is empty, return "".
2) Iterate index i over characters of strs[0].
3) For each other string, if i is out of range or char differs, return strs[0].substring(0, i).
4) If loop completes, first string itself is the common prefix.

Complexity Analysis

Time: O(S), where S is total characters compared before first mismatch.
Space: O(1) extra (excluding output).

Common Pitfalls

- Forgetting empty input array.
- Not handling one string being shorter than current index.
- Returning wrong slice boundary at mismatch.
- Using repeated string concatenation in loops (unnecessary overhead).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";

        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

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

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

    return strs[0]
}

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";

        for (int i = 0; i < (int)strs[0].size(); i++) {
            char c = strs[0][i];
            for (int j = 1; j < (int)strs.size(); j++) {
                if (i == (int)strs[j].size() || strs[j][i] != c) {
                    return strs[0].substr(0, i);
                }
            }
        }

        return strs[0];
    }
};

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        for i, c in enumerate(strs[0]):
            for s in strs[1:]:
                if i == len(s) or s[i] != c:
                    return strs[0][:i]

        return strs[0]

var longestCommonPrefix = function(strs) {
  if (!strs || strs.length === 0) return "";

  for (let i = 0; i < strs[0].length; i++) {
    const c = strs[0][i];
    for (let j = 1; j < strs.length; j++) {
      if (i === strs[j].length || strs[j][i] !== c) {
        return strs[0].slice(0, i);
      }
    }
  }

  return strs[0];
};

中文

题目概述

给定字符串数组 strs，返回它们的最长公共前缀；如果不存在公共前缀，返回空字符串 ""。

核心思路

采用纵向扫描：固定下标 i，比较所有字符串在该位置的字符。只要出现不一致或越界，公共前缀就在 i 之前结束。

暴力解法与不足

暴力方法可以枚举第一个字符串的所有前缀，再逐个检查是否是全部字符串的前缀。实现直观，但会产生大量重复比较。

最优算法步骤

1）若 strs 为空，返回 ""。
2）遍历 strs[0] 的每个下标 i。
3）检查其余字符串：若 i 已越界或字符不等，返回 strs[0][0:i]。
4）若全部位置都通过，说明第一个字符串就是公共前缀。

复杂度分析

时间复杂度：O(S)，S 为比较过的字符总数。
空间复杂度：O(1) 额外空间（不计输出）。

常见陷阱

- 忘记处理空数组输入。
- 没有先判断短字符串越界就直接取字符。
- 失配时切片边界写错（应截到 i 之前）。
- 在循环里频繁拼接字符串，导致不必要开销。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";

        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

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

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

    return strs[0]
}

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";

        for (int i = 0; i < (int)strs[0].size(); i++) {
            char c = strs[0][i];
            for (int j = 1; j < (int)strs.size(); j++) {
                if (i == (int)strs[j].size() || strs[j][i] != c) {
                    return strs[0].substr(0, i);
                }
            }
        }

        return strs[0];
    }
};

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if not strs:
            return ""

        for i, c in enumerate(strs[0]):
            for s in strs[1:]:
                if i == len(s) or s[i] != c:
                    return strs[0][:i]

        return strs[0]

var longestCommonPrefix = function(strs) {
  if (!strs || strs.length === 0) return "";

  for (let i = 0; i < strs[0].length; i++) {
    const c = strs[0][i];
    for (let j = 1; j < strs.length; j++) {
      if (i === strs[j].length || strs[j][i] !== c) {
        return strs[0].slice(0, i);
      }
    }
  }

  return strs[0];
};