Problem Statement
This problem is from Leetcode – Longest Common Prefix. The problem statement is as below:
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 “”
Solution
Lets see the brute force approach:
- Store the first string from the input array in a variable – firstStr.
- Now in a for loop read each character from firstStr and store in another char variable.
- In another nested for loop we’ll iterate through the remaining strings in the input array and check if this char is present at the same index as firstStr.
- If present then we’ll add this character in our prefix variable to be returned as answer.
- Since we are using two nested for loops here, the time complexity of this approach in O(n2)
Lets see the code sample below:
/*
* Input String Array: {"flower","floor","flight"}
*/
public String longestCommonPrefix(String[] strs) {
String prefix = "";
boolean isPresent = true;
// store the first string from the input array in a string variable
String firstStr = strs[0];
/*
* In a for loop read character from firstStr
*/
for(int i=0; i<firstStr.length(); i++) {
// store the char at index i in a variable chr
char chr = firstStr.charAt(i);
/*
* now iterate the input array from the second string
*/
for(int j=1; j<strs.length; j++) {
String curStr = strs[j];
if(curStr.length() > i) {
/*
* here we check if the character chr is present at the same
* index position in this string
*/
if(chr == curStr.charAt(i) ) {
// if yes then store in a boolean variable
isPresent = true;
} // end if
else {
return prefix;
}
} // end if
else {
return prefix;
}
} // end for
if(isPresent) {
// add the character chr in the prefix to be returned
prefix = prefix + chr;
} // end if
} // end for
return prefix;
} // end function
This code returns the following output:
Longest common prefix: fl
You can check out the code from Github here – Longest Common Prefix – First Approach