PROBLEM DESCRIPTION
Given an array of N strings, find the longest common prefix among all strings present in the array. Return “-1” if there is no common prefix.
SOLUTION
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution{
String longestCommonPrefix(String arr[], int n){
// Initialize the longest common prefix with the first string in the array
String lcp = arr[0];
// Iterate through the array of strings starting from the second string
for(int i=1; i<n; i++){
// Update the longest common prefix by finding the common prefix between the current prefix and the next string
lcp = commonPrefix(lcp, arr[i]);
}
// If no common prefix is found, return "-1", otherwise return the longest common prefix
return lcp.equals("") ? "-1" : lcp.toString();
}
// Method to find the common prefix between two strings
String commonPrefix(String s1, String s2){
// Create a StringBuffer to store the common prefix
StringBuffer sb = new StringBuffer();
int i = 0;
// Iterate through the strings as long as there are characters left in both strings and the characters are equal
while(i < s1.length() && i < s2.length() && s1.charAt(i) == s2.charAt(i)){
// Append the current character to the common prefix, and move to next char
sb.append(String.valueOf(s1.charAt(i)));
i++;
}
return sb.toString();
}
}