WikiGalaxy
Longest Common Prefix (LCP)
Understanding LCP
Definition
The Longest Common Prefix (LCP) problem involves finding the longest prefix that is common to all strings in a given array. This is a fundamental problem in computer science, often used in algorithms related to string processing.
Applications
LCP is widely used in applications such as autocompletion, DNA sequencing, and text processing. It serves as a building block for more complex string matching algorithms.
Example 1: Basic Strings
Scenario
Given the strings ["flower", "flow", "flight"], the longest common prefix is "fl".
Explanation
The strings share the prefix "fl". This is determined by comparing characters from each string until a mismatch is found.
public class LCPExample {
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0)
prefix = prefix.substring(0, prefix.length() - 1);
return prefix;
}
public static void main(String[] args) {
String[] words = {"flower", "flow", "flight"};
System.out.println("Longest Common Prefix: " + longestCommonPrefix(words));
}
}
Console Output:
Longest Common Prefix: fl
Example 2: Mixed Length Strings
Scenario
Given the strings ["interspecies", "interstellar", "interstate"], the longest common prefix is "inters".
Explanation
Despite different lengths, the prefix "inters" is common to all strings, highlighting the importance of character-wise comparison.
public class LCPExample {
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0)
prefix = prefix.substring(0, prefix.length() - 1);
return prefix;
}
public static void main(String[] args) {
String[] words = {"interspecies", "interstellar", "interstate"};
System.out.println("Longest Common Prefix: " + longestCommonPrefix(words));
}
}
Console Output:
Longest Common Prefix: inters
Example 3: No Common Prefix
Scenario
Given the strings ["dog", "racecar", "car"], there is no common prefix.
Explanation
The strings do not share a starting sequence of characters, resulting in an empty prefix.
public class LCPExample {
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0)
prefix = prefix.substring(0, prefix.length() - 1);
return prefix;
}
public static void main(String[] args) {
String[] words = {"dog", "racecar", "car"};
System.out.println("Longest Common Prefix: " + longestCommonPrefix(words));
}
}
Console Output:
Longest Common Prefix:
Example 4: Identical Strings
Scenario
Given the strings ["see", "see", "see"], the longest common prefix is "see".
Explanation
All strings are identical, so the entire string is the common prefix.
public class LCPExample {
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0)
prefix = prefix.substring(0, prefix.length() - 1);
return prefix;
}
public static void main(String[] args) {
String[] words = {"see", "see", "see"};
System.out.println("Longest Common Prefix: " + longestCommonPrefix(words));
}
}
Console Output:
Longest Common Prefix: see
Example 5: Single Character Strings
Scenario
Given the strings ["a", "a", "b"], there is no common prefix.
Explanation
Although two strings are identical, the presence of a different character string results in no common prefix.
public class LCPExample {
public static String longestCommonPrefix(String[] strs) {
if (strs == null || strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0)
prefix = prefix.substring(0, prefix.length() - 1);
return prefix;
}
public static void main(String[] args) {
String[] words = {"a", "a", "b"};
System.out.println("Longest Common Prefix: " + longestCommonPrefix(words));
}
}
Console Output:
Longest Common Prefix:
