Problem overview
The method longestCommonPrefix(s1: String, s2: String) returns the longest string that both s1 and s2 start with. A prefix is a piece taken from the beginning, so the answer is the run of characters that match from index 0 until the first difference or the end of the shorter string.
Three examples show the cases. "hello" and "help" agree on h, e and l, then differ (l against p), so the answer is "hel". "Andy" and "Mircea" differ at the first character, so the answer is the empty string. "AlgoCademy" and "Algo" agree on all of the shorter string, so the answer is "Algo".
Approach
Walk through both strings at the same index and compare the characters. As long as they match, the character belongs to the prefix; the first mismatch ends it. A prefix can never be longer than the shorter string, so the loop runs only up to the shorter length. That keeps every index valid in both strings and means the loop can never read past the end of either one.
The prefix is built as you go: a var string starts empty and gets one matching character per pass. When a mismatch appears, the method returns what it has collected so far. If the loop ends without a mismatch, the shorter string is a prefix of the longer one, and the collected string is the shorter string itself.
Step by step
- Find the limit.
val n = scala.math.min(s1.length, s2.length)is the length of the shorter string. - Create the result.
var commonPrefix = ""must be avarbecause it grows during the loop. - Loop over the positions.
for (i <- 0 until n)visits indices 0 ton - 1. The range0 until nexcludesn. - Stop at a mismatch. If
s1(i) != s2(i), returncommonPrefiximmediately. Nothing after a mismatch can belong to the prefix. - Extend the prefix. Reaching the next line means the characters matched, so
commonPrefix += s1(i)adds that character. Taking it froms1is enough becauses2(i)is the same. - Return after the loop. The loop only finishes normally when all
ncharacters matched.
The solution in Scala
class Solution {
def longestCommonPrefix(s1: String, s2: String): String = {
val n = scala.math.min(s1.length, s2.length)
var commonPrefix = ""
for (i <- 0 until n) {
if (s1(i) != s2(i)) {
return commonPrefix
}
commonPrefix += s1(i)
}
return commonPrefix
}
}
Some Scala details:
- Strings are indexed with parentheses.
s1(i)returns aChar, not a one-character string. Square brackets are for type parameters, such asArray[Int]. - Comparing characters.
!=compares the character values. In Scala,==and!=compare contents, also for strings, so there is no need for anequalscall. String += Char.commonPrefix += s1(i)works because+on aStringaccepts any value and appends its text. It creates a new string each time, since strings are immutable.returninsidefor. Scala has nobreakkeyword. The loop body of aforis a function that runs on each element, so thisreturnis a non-local return, implemented by throwing an exception. Scala 3.5 accepts it but prints a warning that non-local returns are no longer supported, so the code works but is flagged for the future. The usual replacement is awhileloop with an index, or finding the first mismatch with a method such asindexWhere.- The last
returnis optional. The last expression of a block is its value, so ending the method withcommonPrefixalone means the same thing. scala.math.min. It is written with its package path here, so no import is needed. Writingmath.minalso works.
Complexity
Let m be the length of the shorter string.
Time: O(m) comparisons. The loop makes at most m passes, and each does a constant amount of comparing. Appending to a string copies it, so the build-up of commonPrefix costs up to 1 + 2 + ... + m character copies, which is O(m²) in the worst case. For short strings this is negligible. For long strings, find the length of the prefix first, then take it with s1.substring(0, length) or s1.take(length) to get O(m) overall.
Space: O(m). The result can be as long as the shorter string.
Edge cases and common mistakes
- One string empty.
nis 0, the loop does not run, and the method returns"". - Identical strings. The whole string comes back, since every position matches.
- One string is a prefix of the other. The loop stops at the shorter length, so there is no index-out-of-bounds error on the longer comparison.
- Looping to the longer length.
s2(i)on an index past the end throwsStringIndexOutOfBoundsException. - Not stopping at the first mismatch. Without the
return, characters after the mismatch could be added when they happen to match, which would give a result that is not a prefix. For"abcx"and"abyx"the answer must be"ab", not"abx". - Case matters.
'A'and'a'are different characters.
Testing
("hello", "help")gives"hel".("Andy", "Mircea")gives"".("AlgoCademy", "Algo")gives"Algo".("", "x")gives"".("abcx", "abyx")gives"ab".
