14. Longest Common Prefix¶
Intuition¶
To find the longest common prefix among all strings in an array, we can take advantage of comparing characters at each position across all strings.\ Since we're looking for a common prefix from the beginning, the moment characters at a particular position don't match across strings, we can stop and return the prefix up to that point.
Complexity¶
| Space Complexity | Time Complexity |
|---|---|
| $\(\text{O}(1)\)$ | $\(\text{O}(nm)\)$ |
Code¶
public String longestCommonPrefix(String[] words) {
// Initialize the maximum possible common prefix length as the length of the first word
int lastMatchingIndex = words[0].length();
// Compare the first word with each of the other words
for (int i = 1; i < words.length; ++i) {
// Reduce the comparison length to the minimum length of both current and previous words
lastMatchingIndex = Math.min(words[i].length(), lastMatchingIndex);
// Compare characters one by one up to the last known matching index
for (int j = 0; j < lastMatchingIndex; ++j) {
if (words[0].charAt(j) != words[i].charAt(j)) {
// Mismatch found; update the last matching index and break
lastMatchingIndex = j;
break;
}
}
}
// Return the longest common prefix from the first word
return words[0].substring(0, lastMatchingIndex);
}