|
In this article, we will find the longest common prefix of two Strings in Java.
Examples:
Input: String 1= horje, String 2 = geezer
Output: “gee”
Input: String 1= flower, String 2 = flight
Output: “fl”
Methods to Find the Longest common Prefix of two Strings in JavaBelow are the methods by which we can find the longest common prefix of two Strings.
- Using a loop to compare characters
- Using the
startsWith method - Using a recursive approach
1. Loop to Compare CharactersHere we use a loop to perform this comparison and construct the longest common prefix by appending matching characters to a StringBuilder. Once a mismatch is encountered, the loop breaks and the method returns the constructed prefix.
Below is the program to Find the Longest common Prefix of two Strings:
Java
public class LongestCommonPrefix {
public static String longestCommonPrefix(String str1, String str2) {
// Find the smaller length between the
// two strings to ensure comparison within bounds
int minLength = Math.min(str1.length(), str2.length());
// Use StringBuilder for efficient string manipulation
StringBuilder prefix = new StringBuilder();
// Loop through both strings until the minimum length
for (int i = 0; i < minLength; i++) {
// Break the loop if characters do not match
if (str1.charAt(i) != str2.charAt(i)) {
break;
}
// Append the matching character to the prefix
prefix.append(str1.charAt(i));
}
// Convert StringBuilder to String and return
return prefix.toString();
}
public static void main(String[] args) {
// Prepare two strings to find their
// longest common prefix
String str1 = "flower";
String str2 = "flight";
// Determine the longest common
// prefix and display it
String longestPrefix = longestCommonPrefix(str1, str2);
System.out.println("Longest Common Prefix: " + longestPrefix);
}
}
OutputLongest Common Prefix: fl
2. startsWith MethodThis method checks if one string starts with another string. It iterates through the characters until a mismatch is found, and then returns the prefix formed by the characters that matched until that index.
Below is the program to Find the Longest common Prefix of two Strings:
Java
public class LongestCommonPrefix {
public static String longestCommonPrefix(String str1, String str2) {
// Determine the minimum length
// between the two strings to limit the comparison
int minLength = Math.min(str1.length(), str2.length());
// Iterate through the strings up to the minimum length
for (int i = 0; i < minLength; i++) {
// If characters at the current index are not
// the same, return the substring up to that point
if (str1.charAt(i) != str2.charAt(i)) {
// Return prefix until mismatch
return str1.substring(0, i);
}
}
// If all characters match up to the
// minimum length, return the entire substring
return str1.substring(0, minLength);
// Return prefix if no mismatch
}
public static void main(String[] args) {
// Initialize two strings for comparison
String str1 = "flower";
String str2 = "flight";
// Call the method to find and
// print the longest common prefix
String longestPrefix = longestCommonPrefix(str1, str2);
System.out.println("Longest Common Prefix: " + longestPrefix);
}
}
OutputLongest Common Prefix: fl
3. Recursive approachIf the substrings at a certain length are equal, it returns that substring as the common prefix. Otherwise, it recursively calls itself with a smaller length until it finds the longest common prefix.
Below is the program to Find the Longest common Prefix of two Strings:
Java
public class LongestCommonPrefix {
public static String longestCommonPrefix(String str1, String str2) {
// Initialize the minimum length variable
// with the minimum of the two string lengths
int minLength = Math.min(str1.length(), str2.length());
// Call the recursive method to find the longest common prefix
return longestCommonPrefixRecursive(str1, str2, minLength);
}
private static String longestCommonPrefixRecursive(String str1, String str2, int length) {
// if length is 0
// return an empty string
if (length == 0) {
return "";
}
// If the substrings of the current
// length are equal, return the substring
else if (str1.substring(0, length).equals(str2.substring(0, length))) {
return str1.substring(0, length);
} else {
// Otherwise, decrease the length
// by 1 and call the method recursively
return longestCommonPrefixRecursive(str1, str2, length - 1);
}
}
public static void main(String[] args) {
// Define two strings to find their longest common prefix
String str1 = "flower";
String str2 = "flight";
// Call the method to find the longest common prefix and print it
String longestPrefix = longestCommonPrefix(str1, str2);
System.out.println("Longest Common Prefix: " + longestPrefix);
}
}
OutputLongest Common Prefix: fl
|
