Algorithm
Problem Name: 14. Longest Common Prefix
Problem Link: https://leetcode.com/problems/longest-common-prefix/
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 "".
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.
Constraints:
1 <= strs.length <= 2000 <= strs[i].length <= 200strs[i]consists of only lowercase English letters.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
char* longestCommonPrefix(char** strs, int strsSize) {
int i, n = 0;
char c;
if (strsSize == 0) return "";
while (c = strs[0][n]) {
for (i = 1; i < strsSize; i ++) {
if (strs[i][n] != c) {
strs[0][n] = 0;
return strs[0];
}
}
n ++;
}
strs[0][n] = 0;
return strs[0];
}
Input
strs = ["flower","flow","flight"]
Output
"fl"
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
string res = strs[0];
for(auto s: strs) res = match(res, s);
return res;
}
string match(const string& pre, const string& s){
int i = 0, len = min(pre.size(), s.size());
for(; i < len; i++) if(s[i] != pre[i]) break;
return pre.substr(0, i>;
}
};
Input
strs = ["dog","racecar","car"]
Output
""
#3 Code Example with Java Programming
Code -
Java Programming
public String longestCommonPrefix(String[] strs) {
int minLength = Integer.MAX_VALUE;
int minLengthIdx = -1;
for (int i = 0; i < strs.length; i++) {
if (strs[i].length() < minLength) {
minLength = strs[i].length();
minLengthIdx = i;
}
}
StringBuilder sb = new StringBuilder();
for (int i = 0; i < strs[minLengthIdx].length(); i++) {
for (String str : strs) {
if (str.charAt(i) != strs[minLengthIdx].charAt(i)) {
return sb.toString();
}
}
sb.append(strs[minLengthIdx].charAt(i));
}
return sb.toString();
}
}
Input
strs = ["flower","flow","flight"]
Output
"fl"
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const longestCommonPrefix = function(strs) {
const A = strs.concat().sort(),
a1 = A[0] || "",
a2 = A[A.length - 1] || "",
L = a1.length,
i = 0;
while (i < L && a1.charAt(i) === a2.charAt(i)) i++;
return a1.substring(0, i);
};
Input
strs = ["dog","racecar","car"]
Output
""
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def longestCommonPrefix(self, s: List[str]) -> str:
j = 0
while s and all(j < len(s[i]) and j < len(s[i - 1]) and s[i][j] == s[i - 1][j] for i in range(len(s))):
j += 1
return s[0][:j] if j else ''
Input
strs = ["flower","flow","flight"]
Output
"fl"
#6 Code Example with C# Programming
Code -
C# Programming
namespace LeetCode
{
public class _014_LongestCommonPrefix
{
public string LongestCommonPrefix(string[] strs)
{
if (strs.Length == 0) { return string.Empty; }
if (strs.Length == 1) { return strs[0]; }
var index = 0;
bool isSame = true;
var firstString = strs[0];
for (index = 0; index < firstString.Length; index++)
{
for (int i = 1; i < strs.Length; i++)
{
if (strs[i].Length <= index ||
strs[i][index] != firstString[index])
{
isSame = false;
break;
}
}
if (!isSame)
{
break;
}
}
return firstString.Substring(0, index);
}
}
}
Input
strs = ["dog","racecar","car"]
Output
""