Description:
Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".
Examples:
Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"
Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.Solution in Python:
Steps to Solve the Problem:
- Check for Empty Input:
- If the input list
strsis empty, return an empty string.
- If the input list
- Initialize the Prefix:
- Assume the first string is the common prefix initially.
- Compare the Prefix with Each String:
- Iterate through the rest of the strings in the list.
- For each string, compare characters one by one with the current prefix.
- If a character doesn’t match, reduce the prefix length accordingly.
- Stop comparing when the prefix becomes empty or we reach the end of the string.
- Return the Result:
- Return the common prefix after comparing all strings.
Python
from typing import List
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
# If the list is empty, return an empty string
if not strs:
return ""
# Assume the first string is the common prefix
prefix = strs[0]
# Compare the prefix with each string in the list
for s in strs[1:]:
# Find the minimum length between the prefix and the current string
min_length = min(len(prefix), len(s))
# Initialize a new prefix to build
new_prefix = ""
# Compare characters one by one
for i in range(min_length):
if prefix[i] == s[i]:
new_prefix += prefix[i]
else:
break
# Update the prefix
prefix = new_prefix
# If at any point the prefix is empty, return immediately
if not prefix:
return ""
return prefixExplanation of the Code:
- Check for Empty Input:
- The condition
if not strs:checks if the input list is empty and returns an empty string if true.
- The condition
- Initialize the Prefix:
- The variable
prefixis initialized to the first string in the liststrs[0].
- The variable
- Compare the Prefix with Each String:
- The
for s in strs[1:]:loop iterates through each string in the list starting from the second string. - Inside the loop,
min_lengthis the minimum length between the current prefix and the current string to avoid index out of range errors. - The
new_prefixis initialized as an empty string to build the new common prefix character by character. - The inner
for i in range(min_length):loop compares each character of the prefix with the current string. If they match, the character is added tonew_prefix. If they don’t match, the loop breaks.
- The
- Update and Check the Prefix:
- After comparing characters,
prefixis updated tonew_prefix. - If
prefixbecomes empty at any point (if not prefix:), return an empty string immediately.
- After comparing characters,
- Return the Result:
- After the loop finishes,
prefixcontains the longest common prefix, which is returned.
- After the loop finishes,
This method ensures we handle the longest common prefix efficiently by comparing characters of the strings iteratively and updating the prefix accordingly.
Solution in Javascript:
JavaScript
/**
* @param {string[]} strs
* @return {string}
*/
var longestCommonPrefix = function(strs) {
// If the list is empty, return an empty string
if (!strs.length) {
return "";
}
// Assume the first string is the common prefix
let prefix = strs[0];
// Compare the prefix with each string in the list
for (let i = 1; i < strs.length; i++) {
let currentString = strs[i];
let j = 0;
// Compare characters one by one
while (j < prefix.length && j < currentString.length && prefix[j] === currentString[j]) {
j++;
}
// Update the prefix to the common part
prefix = prefix.substring(0, j);
// If at any point the prefix is empty, return immediately
if (prefix === "") {
return "";
}
}
return prefix;
};Solution in Java:
Java
class Solution {
public String longestCommonPrefix(String[] strs) {
// If the array is empty, return an empty string
if (strs == null || strs.length == 0) {
return "";
}
// Assume the first string is the common prefix
String prefix = strs[0];
// Compare the prefix with each string in the array
for (int i = 1; i < strs.length; i++) {
String currentString = strs[i];
int j = 0;
// Compare characters one by one
while (j < prefix.length() && j < currentString.length() && prefix.charAt(j) == currentString.charAt(j)) {
j++;
}
// Update the prefix to the common part
prefix = prefix.substring(0, j);
// If at any point the prefix is empty, return immediately
if (prefix.isEmpty()) {
return "";
}
}
return prefix;
}
}Solution in C#:
C#
public class Solution {
public string LongestCommonPrefix(string[] strs) {
// If the array is null or empty, return an empty string
if (strs == null || strs.Length == 0) {
return "";
}
// Assume the first string is the common prefix
string prefix = strs[0];
// Compare the prefix with each string in the array
for (int i = 1; i < strs.Length; i++) {
string currentString = strs[i];
int j = 0;
// Compare characters one by one
while (j < prefix.Length && j < currentString.Length && prefix[j] == currentString[j]) {
j++;
}
// Update the prefix to the common part
prefix = prefix.Substring(0, j);
// If at any point the prefix is empty, return immediately
if (string.IsNullOrEmpty(prefix)) {
return "";
}
}
return prefix;
}
}