1. Don't think too much about performance.
Worst performance problems arise because the coder thought something could be faster but she didn't consider that the JVM does runtime optimizations for her code.
So always prefer writing readable code that works. Only step into performance optimization if you actually faced a performance issue and you have proven by measurement that this particular piece of code is the problem and the alternative approach really solves the problem.
2. Why are you inventing the wheel a 4th time?
The JVM has methods to compare strings. There is even a startsWith() method that would perfectly fit.
3 Structure your code
Your code has 2 obvious parts. The first one you marked with an inline comment.
Better use methods with good names for this kind of structuring.
An alternative solution could look like this:
My solution made some assumption on the behavior of the methods in the String class which I verified with spikes coded as JUnit Tests along with the acceptance test using your given example.
import static org.junit.jupiter.api.Assertions.*;
import org.junit.jupiter.api.Test;
class LongestCommonPrefixTest {
@Test
void spike__does_StartsWith_returnTrueForTheEmptyString() {
assertTrue("someWord".startsWith(""));
}
@Test
void spike__does_substring_returnTheEmptyStringForEndIndexZero() {
assertEquals("", "someWord".substring(0, 0));
}
@Test
void spike__does_substring_returnShorterStringForLengthMinus1() {
String someWord = "someWord";
assertEquals("someWor", someWord.substring(0, someWord.length() - 1));
}
@Test
void acceptanceTest() throws Exception {
String[] strs = { "flower", "flow", "flight" };
String longestCommonPrefix = //
new LongestCommonPrefix().longestCommonPrefix(strs);
assertEquals("fl", longestCommonPrefix);
}
}
And this is the solution I came up with:
public class LongestCommonPrefix {
public String longestCommonPrefix(String[] strs) {
String currentPrefix = selectFirstWordOrEmptyString(strs);
for (String currentWord : strs) {
currentPrefix = findCommonPrefixIn(currentPrefix, currentWord);
}
return currentPrefix;
}
private String selectFirstWordOrEmptyString(String[] strs) {
return 0 == strs.length ? "" : strs[0];
}
private String findCommonPrefixIn(String currentPrefix, String currentWord) {
while (!currentWord.startsWith(currentPrefix)) {
currentPrefix = currentPrefix.substring(0, currentPrefix.length() - 1);
}
return currentPrefix;
}
}
A performance improvement could be possible if you always pass the shorter of currentPattern and currentWord as first parameter to the private method and the longer one as second. But as I wrote you shouldn't do that unless necessary.
