The code does not use a trie, so it would appear to fail the requirements out of the gate.
I have several concerns with the layout of the code:
- Indentation is inconsistent. In particular, code inside a method should be indented.
- Curly braces, though technically optional, make code much easier to read. They can also prevent errors when editing existing code.
- When present, closing curly braces belong on a line by themselves. They should not be on the same line as the block they're closing.
- In my opinion,
var is being overused. The design intent of var is to keep code from having to declare a type on both sides of an assignment. It was not intended as a blanket means of avoiding declaring type. Code is harder to read when the type is not obvious on at least one side of the assignment operator. Source
The use of meaningful variable names is very good and greatly enhances the readability of this code.
Unit tests make it easier to see exactly how the code is behaving and to make sure failures aren't introduced as code gets modified. Especially for problems of this type, you might consider learning about Test-Driven Development (TDD).
I do not see the value in the contains() call. If there is no common prefix, getCommonPrefixOf returns "", which is what longestCommonPrefix() is returning anyway.
It would be preferable to validate words as close to when the user provides it as possible. This is slightly more performant, and the helper method doesn't have as much work to do.
Validating words.length <= 1 is misleading, because it implies that the code hasn't checked its size is zero. It also won't behave properly if the size actually is zero.
The check on second for index > 1 is somewhat inefficient and confusing to read. It would be preferable for longestCommonPrefix to just start the index at 1 and make the first prefix words[0]. Then, the code doesn't need the concept of first or second at all. It can just compare words[index] to prefix. It might be easier to read with a currentWord variable.
I'm assuming the contract states the code should return "" if any word is null. That would typically be specified in Javadoc, which is not useful for toy problems except when people are asked to review the code and don't have the contract. :)
The StringBuilder's name is uninspiring. Fortunately, the StringBuilder is superfluous. The code can instead use substring().
The code should break out of the for loop early once no match has been detected. Otherwise aaxbb and aaybb will report a common prefix of aabb. Refactoring it looks a bit ugly if we try to keep it inline, because we need to track the loop index outside the loop. A nice way to deal with that is to extract the loop into a helper method, which can then return the index from inside the loop.
Avoid situations where the difference between variable++ and ++variable will matter. Use variable + 1 if the value of the variable itself does not need to change.
If you made all these changes, your code might look more like:
public class Test {
public static void main(String[] argv) {
Test test = new Test();
System.out.println("empty array? " + "".equals(test.longestCommonPrefix(new String[0])));
System.out.println("one word?? " + "a".equals(test.longestCommonPrefix(new String[]{"a"})));
System.out.println("no common prefix? "
+ "".equals(test.longestCommonPrefix(new String[]{"a", "b"})));
System.out.println("short common prefix? "
+ "a".equals(test.longestCommonPrefix(new String[]{"aa", "ab"})));
System.out.println("long common prefix? "
+ "abcde".equals(test.longestCommonPrefix(new String[]{"abcdef", "abcdeg", "abcdefg"})));
System.out.println("test interrupt? "
+ "aa".equals(test.longestCommonPrefix(new String[]{"aaxbb", "aaybb", "aazbb"})));
System.out.println("perfect match? "
+ "aaxbb".equals(test.longestCommonPrefix(new String[]{"aaxbb", "aaxbb", "aaxbb"})));
System.out.println("one null word? "
+ "".equals(test.longestCommonPrefix(new String[]{"aa", null})));
System.out.println("two words w/ null? "
+ "".equals(test.longestCommonPrefix(new String[]{"aa", null})));
System.out.println("three words w/ null? "
+ "".equals(test.longestCommonPrefix(new String[]{"aa", "ab", null})));
}
public String longestCommonPrefix(String[] words) {
if (words == null || words.length == 0) {
return "";
}
if (words.length == 1) {
return words[0] == null ? "" : words[0];
}
return getCommonPrefixOf(words, 1, words[0]);
}
private String getCommonPrefixOf(String[] words, int index, String prefix) {
if (index == words.length) {
return prefix;
}
String currentWord = words[index];
if (currentWord == null) {
return "";
}
int firstNonmatchingIndex = firstNonmatchingIndexOf(currentWord, prefix);
return getCommonPrefixOf(words, index + 1, currentWord.substring(0, firstNonmatchingIndex));
}
/**
* Returns the first index where the two inputs do not have a matching character.
* Ex.
* <pre>
* firstNonmatchingIndexOf("", "b") -> 0
* firstNonmatchingIndexOf("a", "b") -> 0
* firstNonmatchingIndexOf("aab", "aac") -> 2
* </pre>
* @throws NullPointerException if either parameter is null.
*/
private static int firstNonmatchingIndexOf(String s1, String s2) {
int maxLength = Math.min(s1.length(), s2.length());
for (int i = 0; i < maxLength; i++) {
if (s1.charAt(i) != s2.charAt(i)) {
return i;
}
}
return maxLength;
}
}
I do not believe that a recursive solution is optimal here. I think that using a nested loop would be significantly easier to read:
public class Test {
public static void main(String[] argv) {
Test test = new Test();
System.out.println("empty array? " + "".equals(test.longestCommonPrefix(new String[0])));
System.out.println("one word?? " + "a".equals(test.longestCommonPrefix(new String[]{"a"})));
System.out.println("no common prefix? "
+ "".equals(test.longestCommonPrefix(new String[]{"a", "b"})));
System.out.println("short common prefix? "
+ "a".equals(test.longestCommonPrefix(new String[]{"aa", "ab"})));
System.out.println("long common prefix? "
+ "abcde".equals(test.longestCommonPrefix(new String[]{"abcdef", "abcdeg", "abcdefg"})));
System.out.println("test interrupt? "
+ "aa".equals(test.longestCommonPrefix(new String[]{"aaxbb", "aaybb", "aazbb"})));
System.out.println("perfect match? "
+ "aaxbb".equals(test.longestCommonPrefix(new String[]{"aaxbb", "aaxbb", "aaxbb"})));
System.out.println("one null word? "
+ "".equals(test.longestCommonPrefix(new String[]{"aa", null})));
System.out.println("two words w/ null? "
+ "".equals(test.longestCommonPrefix(new String[]{"aa", null})));
System.out.println("three words w/ null? "
+ "".equals(test.longestCommonPrefix(new String[]{"aa", "ab", null})));
}
public String longestCommonPrefix(String[] words) {
if (words == null || words.length == 0) {
return "";
}
if (words.length == 1) {
return words[0] == null ? "" : words[0];
}
String prefix = words[0];
for (int i = 1; i < words.length; i++) {
if (words[i] == null) {
return "";
}
int firstNonmatchingIndex = firstNonmatchingIndexOf(prefix, words[i]);
if (firstNonmatchingIndex < prefix.length()) {
prefix = prefix.substring(0, firstNonmatchingIndex);
}
}
return prefix;
}
/**
* Returns the first index where the two inputs do not have a matching character.
* Ex.
* <pre>
* firstNonmatchingIndexOf("", "b") -> 0
* firstNonmatchingIndexOf("a", "b") -> 0
* firstNonmatchingIndexOf("aab", "aac") -> 2
* </pre>
* @throws NullPointerException if either parameter is null.
*/
private static int firstNonmatchingIndexOf(String s1, String s2) {
int maxLength = Math.min(s1.length(), s2.length());
for (int i = 0; i < maxLength; i++) {
if (s1.charAt(i) != s2.charAt(i)) {
return i;
}
}
return maxLength;
}
}
