Problem overview
The method longestCommonPrefix(_ s1: String, _ s2: String) returns the longest string that both inputs start with. For "hello" and "help" the answer is "hel": the first three characters match, and the fourth differs (l against p). For "Andy" and "Mircea" the first characters already differ, so the result is the empty string. For "AlgoCademy" and "Algo" the shorter string is itself a prefix of the longer one, so the answer is "Algo".
Approach
Walk through both strings from the start, comparing the characters at the same position. As long as they are equal, they belong to the prefix. At the first mismatch, stop: nothing after it can be part of a prefix. Two things bound the walk. It can't go past the end of the shorter string, because that string has no characters left to compare. And once it ends, whatever was collected so far is the answer.
In many languages you would index straight into the strings. Swift does not allow s1[i] with an integer, because a String is a sequence of characters of varying byte length and reaching position i would mean walking from the start. The standard fix is to convert each string once into an Array of Character values, which can be indexed in constant time.
Step by step
- Find the limit.
let n = min(s1.count, s2.count)is the number of positions both strings have. Looping up tonkeeps every index valid in both. - Start with an empty result.
var commonPrefix = ""must be avar, since it grows. - Make character arrays.
Array(s1)andArray(s2)give[Character]values, soa1[i]works. The reference declares both on oneletline, separated by a comma. - Loop over the positions with
for i in 0..<n. The half-open range stops beforen, which is exactly the last valid index plus one. - Stop at a mismatch. If
a1[i] != a2[i],breakleaves the loop. The prefix can't continue past a difference. - Append the matching character. We only reach this line when the characters are equal, so taking it from
s1is enough.String(a1[i])turns theCharacterinto aStringso that+=has strings on both sides. - Return the result after the loop. It runs after a
breakand also when allnpositions matched.
The solution in Swift
class Solution {
func longestCommonPrefix(_ s1: String, _ s2: String) -> String {
let n = min(s1.count, s2.count)
var commonPrefix = ""
let a1 = Array(s1), a2 = Array(s2)
for i in 0..<n {
if a1[i] != a2[i] {
break
}
commonPrefix += String(a1[i])
}
return commonPrefix
}
}
Swift details worth knowing:
- No integer subscript on strings. Writing
s1[i]is a compile error.Array(s1)is the usual way around it when you need positions. countcounts characters. ACharacteris one user-perceived character, which can be made of several Unicode scalars, such as an accented letter written with a combining mark.countand the arrays agree with each other because both use characters, so the indices line up.- Characters compare with
!=. TwoCharactervalues compare by value, and the comparison is case-sensitive:"A"and"a"are different. CharacterversusString. Appending aCharacterto aStringwith+=doesn't compile, which is why the code wraps it inString(...).breakonly exits the loop, not the method, so thereturnafter the loop still runs.
An alternative with zip
Swift can pair up two sequences with zip, which stops at the end of the shorter one. That removes the need for min, the arrays and the indices:
func lcp2(_ s1: String, _ s2: String) -> String {
var result = ""
for (c1, c2) in zip(s1, s2) {
if c1 != c2 { break }
result.append(c1)
}
return result
}
It returns "hel" for "hello" and "help", "Algo" for "AlgoCademy" and "Algo", and an empty string when one input is empty. The lesson's index-based version is still the one to learn first, because it practises the pattern you will need whenever you must compare or move positions in a string: convert to an array, then index.
Complexity
Time: O(m + n) for string lengths m and n, mostly because converting each string to an array and counting characters visits every character once. The comparison loop itself runs at most min(m, n) times. Space: O(m + n), for the two arrays, plus up to min(m, n) characters for the result.
Edge cases and common mistakes
- An empty string. If either input is empty,
nis 0, the loop body never runs, and the result is"". - Identical strings. No mismatch occurs, so the whole string is returned.
- One string is a prefix of the other. The loop ends at the end of the shorter string, without reading past it. Looping up to
maxinstead ofminwould read beyond the end of the shorter array and crash the program. - Case.
"Apple"and"apple"share no prefix, so the answer is empty. - Forgetting
break. Without it, the loop would skip the mismatched position and continue appending later matching characters, producing a string that is not a prefix. - Mixing up
StringandCharacter.commonPrefix += a1[i]doesn't compile; the conversion is needed.
Testing
"hello","help"gives"hel"."Andy","Mircea"gives""."AlgoCademy","Algo"gives"Algo"."","abc"gives""."same","same"gives"same".
