Question 7
Back to Exercise
Find the longest common prefix of an array of strings by shortening a candidate prefix until every string starts with it.
Solution
public class Main {
static String lcp(String[] words) {
if (words.length == 0) return "";
String prefix = words[0];
for (String w : words) {
while (!w.startsWith(prefix)) prefix = prefix.substring(0, prefix.length() - 1);
}
return prefix;
}
public static void main(String[] args) {
System.out.println("[" + lcp(new String[]{"interview", "internet", "interval", "internal"}) + "]");
System.out.println("[" + lcp(new String[]{"java", "javascript", "jar"}) + "]");
System.out.println("[" + lcp(new String[]{"apple", "banana"}) + "]");
}
}
[inter] [ja] []
The prefix only ever shrinks, and the empty string is a prefix of everything, so the loop always ends.
Discussion & Comments 0
Share your method, a shortcut, or ask about a step you didn't follow.
No comments yet. Be the first to share your solution!