Page tree
Go to start of banner

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: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""

Explanation: There is no common prefix among the input strings.
Note:

All given inputs are in lowercase letters a-z.

Solution 1 in C++

```class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
int arraySize = strs.size();
if (arraySize<1) eturn "";

int i;
int s_len=strs[0].length();
int prefixIndex=0;
while(prefixIndex<s_len) {
for(i=1;i<arraySize;i++) {
if (strs[0][prefixIndex]!=strs[i][prefixIndex]) break;
}
if (i<arraySize) break;
prefixIndex++;
}
if (prefixIndex) return strs[0].substr(0,prefixIndex);
return "";
}
};```

Solution 2 in Java - Complexity O(1), Time Complexity O(S)

```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];
}```

• No labels