14. Longest Common Prefix Leetcode Solution
Longest Common Prefix Leetcode Problem :
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 :
Input: strs = ["flower","flow","flight"]
Output: "fl"
Longest Common Prefix Leetcode Solution :
Constraints :
- 1 <= strs.length <= 200
- 0 <= strs[i].length <= 200
- strs[i] consists of only lowercase English letters.
Example 1:
- Input: strs = [“dog”,”racecar”,”car”]
- Output: “”
Approach :
- Initialize an empty string ans to store the common prefix.
- Sort the input list v lexicographically. This step is necessary because the common prefix should be common to all the strings, so we need to find the common prefix of the first and last string in the sorted list.
- Iterate through the characters of the first and last string in the sorted list, stopping at the length of the shorter string.
- If the current character of the first string is not equal to the current character of the last string, return the common prefix found so far.
- Otherwise, append the current character to the ans string.
- Return the ans string containing the longest common prefix.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
C++
Java
Python
C++
class Solution {
public:
string longestCommonPrefix(vector< string>& v) {
string ans="";
sort(v.begin(),v.end());
int n=v.size();
string first=v[0],last=v[n-1];
for(int i=0;i< min(first.size(),last.size());i++){
if(first[i]!=last[i]){
return ans;
}
ans+=first[i];
}
return ans;
}
};
Java
class Solution {
public String longestCommonPrefix(String[] v) {
StringBuilder ans = new StringBuilder();
Arrays.sort(v);
String first = v[0];
String last = v[v.length-1];
for (int i=0; iPython
class Solution:
def longestCommonPrefix(self, v: List[str]) -> str:
ans=""
v=sorted(v)
first=v[0]
last=v[-1]
for i in range(min(len(first),len(last))):
if(first[i]!=last[i]):
return ans
ans+=first[i]
return ans
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment