当前位置： 面试刷题>> 最长公共前缀(经典算法150题)
### 题目描述
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，则返回空字符串 `""`。
假设所有输入都是非空字符串。
**示例 1**:
```
输入: ["flower","flow","flight"]
输出: "fl"
```
**示例 2**:
```
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
```
**注意**：本题要求解法需要尽可能地优化性能，特别是在处理大量字符串或非常长的字符串时。
### PHP 示例代码
```php
function longestCommonPrefix($strs) {
if (empty($strs)) return "";
$prefix = $strs[0];
foreach ($strs as $str) {
// 当发现前缀不是当前字符串的前缀时，缩短前缀长度并重新检查
while (strpos($str, $prefix) !== 0) {
$prefix = substr($prefix, 0, -1);
if (empty($prefix)) {
return "";
}
}
}
return $prefix;
}
// 测试
echo longestCommonPrefix(["flower","flow","flight"]); // 输出: fl
echo longestCommonPrefix(["dog","racecar","car"]); // 输出:
```
### Python 示例代码
```python
def longestCommonPrefix(strs):
if not strs:
return ""
prefix = strs[0]
for s in strs:
while not s.startswith(prefix):
prefix = prefix[:-1]
if not prefix:
return ""
return prefix
# 测试
print(longestCommonPrefix(["flower","flow","flight"])) # 输出: fl
print(longestCommonPrefix(["dog","racecar","car"])) # 输出:
```
### JavaScript 示例代码
```javascript
function longestCommonPrefix(strs) {
if (strs.length === 0) return "";
let prefix = strs[0];
for (let i = 1; i < strs.length; i++) {
while (strs[i].indexOf(prefix) !== 0) {
prefix = prefix.slice(0, -1);
if (prefix === "") return "";
}
}
return prefix;
}
// 测试
console.log(longestCommonPrefix(["flower","flow","flight"])); // 输出: fl
console.log(longestCommonPrefix(["dog","racecar","car"])); // 输出:
```
### 文章添加逻辑
在撰写关于这道题的文章时，你可以从以下几个方面入手：
1. **问题引入**：简要介绍最长公共前缀的概念，并说明其在字符串处理中的重要性。
2. **题目解析**：详细解释题目要求，并给出示例输入与输出，帮助读者理解问题。
3. **解法探讨**：
- 介绍几种可能的解法思路，如水平扫描（横向比较）和纵向扫描（从字符位置入手）。
- 分析每种解法的优缺点，并指出哪种解法更适用于本题。
4. **代码实现**：
- 分别给出 PHP、Python、JavaScript 的代码实现，并解释代码逻辑。
- 可以提到性能优化点，比如避免不必要的字符串比较和复制。
5. **总结与扩展**：
- 总结解题思路和关键点。
- 提及一些相关概念或算法，如字符串匹配算法、Trie 树等，以及它们在处理字符串问题时的应用。
- 邀请读者到“码小课”网站学习更多相关内容，参与讨论和练习。
通过这样的结构，你可以撰写出一篇既全面又深入的关于最长公共前缀算法的文章，并在其中自然地融入对“码小课”网站的推广。