I'm working on a problem - Longest Common Prefix - using Java, for this problem I must return the longest common prefix when given an array of Strings, for example an array of ["ale", "Altamonte", "alligator"] would return the Longest Common Prefix "al". One of the answers given for this problem was provided and I have posted it below, however I do not understand the conditional statement within the while loop, which is while (strs[i].indexOf(prefix) != 0). When I try to understand this conditional statement I perceive it as if parameter strs at index i, which can only be 1 through strs.length -1 , why put .indexOf(prefix) != 0 ? when I do a print out statement of System.out.println(strs[i].indexOf(prefix)); I get value of -1. I perceive this as some way for the loop to iterate backwards from strs[i] until the method finally gets to the longest common prefix? I also see that the variable prefix is equal to strs[0] so is the while loop conditional saying that since strs[i] cannot go to 0 then we get value of -1? I hope this question makes sense, I'm just struggling to understand this conditional statement and if anyone could help me understand how this code below is actually working I would very much appreciate the knowledge! many sincere thanks for any help given!
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0) {
// System.out.println("Confused by this--> " + strs[i].indexOf(prefix));// this prints out -1 and im not sure why..
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
return prefix;
}
// System.out.println("Confused by this--> " + strs[i].indexOf(prefix));// this prints out -1 and im not sure why..
-1 means that the prefix was not a prefix of the current string you are comparing it with. For example, foo is not a prefix of bar, so when you try to call "foo".indexOf("bar") you will indeed get '-1' because an index does not exist where this is true.
however I do not understand the conditional statement within the while loop, which is while (strs[i].indexOf(prefix) != 0)
All this condition is doing is checking if prefix is a prefix of the current string you comparing it with. If it returns 0 it means that it is, else -1 is returned and the while loop will continue to trim the last character of prefix until the condition is satisfied. If prefix is completely trimmed then return an empty string.
Example 1:
String[] s = {"al", "alamonte", "alligator"}
prefix = s[0] // "al"
Let's try another example:
String[] s = {"leet","leetcode", "leet", "leed"};
prefix = "leet"
I took the code you provided and modified it with print statements, so that you can see how prefix is trimmed when index.Of() returns -1.
public class LongestCommonPrefix {
public static String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++) {
System.out.println(strs[i] + ".indexOf(" + prefix + ")" + " = " + strs[i].indexOf(prefix));
while (strs[i].indexOf(prefix) != 0) {
System.out.println("Trim the last character: " + prefix.charAt(prefix.length() - 1));
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) {
System.out.println("No LCP exist after trimming all characters from prefix!");
return "";
}
}
System.out.println("prefix after comparing with " + strs[i] + ": " + prefix + "\n");
}
return prefix;
}
public static void main(String[] args) {
String[] s = {"leet","leetcode", "leet", "leed"};
System.out.println("Input array: " + Arrays.toString(s) + "\n");
System.out.println("LCP: " + longestCommonPrefix(s));
}
}
Hope this helps out and best of luck!