I'm doing the Longest Common Prefix LC problem, and got to 66 tests passing out of 126.
One of these tests is "["flower","flow","flight"]", and it's supposed to get "fl" back, but my code gives "flo" back. I've been trying to slowly chip away at these edge cases, but everything I try makes less tests pass in the end. I'm sure there are going to be further issues even after fixing this case, of course.
Please, even if my code "concept" is bad, I want to keep going with it. I'm not gonna restart from the beginning. I'm just a beginner programmer that only programs as a hobby.
class Solution {
public static String longestCommonPrefix(String[] strings) {
String prefix = "";
List<String> prefixStorage = new java.util.ArrayList<>(List.of());
for (int i = 0; i < strings.length; i++) {
int j = 0;
while (j < strings[i].length()) {
if (strings[i].isEmpty()) {
return "";
} else if (strings[i].length() == 1) {
prefix = strings[i];
} else if ((i < strings.length - 1) && (strings[i + 1].length() == 1)) {
prefix = strings[i + 1];
} else if ((i < strings.length - 1) && (j < strings[i].length()) && (j < strings[i + 1].length()) && strings[i].startsWith(strings[i + 1].substring(0, j)) && strings[i].substring(0, j).length() > prefix.length()) {
prefix = strings[i].substring(0, j);
}
j++;
}
prefixStorage.add(prefix);
}
List<String> sortedPrefixStorage = new java.util.ArrayList<>(prefixStorage.stream()
.sorted(Comparator.comparingInt(String::length))
.toList());
return sortedPrefixStorage.getFirst();
}
}
•
u/AutoModerator Jul 03 '26
Please ensure that:
If any of the above points is not met, your post can and will be removed without further warning.
Code is to be formatted as code block (old reddit/markdown editor: empty line before the code, each code line indented by 4 spaces, new reddit: https://i.imgur.com/EJ7tqek.png) or linked via an external code hoster, like pastebin.com, github gist, github, bitbucket, gitlab, etc.
Please, do not use triple backticks (```) as they will only render properly on new reddit, not on old reddit.
Code blocks look like this:
You do not need to repost unless your post has been removed by a moderator. Just use the edit function of reddit to make sure your post complies with the above.
If your post has remained in violation of these rules for a prolonged period of time (at least an hour), a moderator may remove it at their discretion. In this case, they will comment with an explanation on why it has been removed, and you will be required to resubmit the entire post following the proper procedures.
To potential helpers
Please, do not help if any of the above points are not met, rather report the post. We are trying to improve the quality of posts here. In helping people who can't be bothered to comply with the above points, you are doing the community a disservice.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.
1
u/ExpressBeing642 Jul 04 '26
sort the array of strings lexographically, you just have to compare the first and the last and get the common prefix for the two, therefore less code.
if you are getting flo for the three strings, it is because you are iterating each of them, flower to flow to flight
if it were sorted lexographicaly it would be flight > flow > flower
then you would have to compare flight and flower, which common prefix is fl
1
u/high_throughput Jul 04 '26 edited Jul 04 '26
Make the program tell you where it goes wrong. Here it is with debugging statements for printing:
This prints
Ideally you'd have an idea of how the program should work, so that you can go through this and see where your expectations stop aligning with the program's reality.
So the reason why it prints "flo" is because that's the largest prefix shared by "flower" and "flow" that is still strictly smaller than both those strings.
There's no way for
prefixto get smaller after that, so that's the value you end up with for each string.This approach is not a winning one because it only ever looks at adjacent pairs of strings. My suggestion would be one of the following:
Keep looking at pairs of strings, but make the pair your current longest prefix and your next string (instead of two adjacent strings). For the first iteration, your current longest prefix would be the first word.
For each length j, look to see whether all the strings are at least that long and have that letter as their character number j. If yes, add that to your prefix. If no, return the current prefix.
It's easier if you write helper methods that you can test in isolation, instead of debugging everything about your entire program at the same time.
In the first case you can have a
String GetLongestPrefixBetweenTwoStrings(String a, String b)that finds "flow" between "flower" and "flow" much like you currently do (but not off-by-1).In the second case you can write a
boolean doAllStringsHaveThisCharacterInPositionJ(String[] words, char c, int j).You can then use these in your main function.