Skip to content

Instantly share code, notes, and snippets.

@kracekumar
Last active May 5, 2025 21:51
Show Gist options
  • Save kracekumar/07b1e138ede9b15b6662cb58b29f67f4 to your computer and use it in GitHub Desktop.
Save kracekumar/07b1e138ede9b15b6662cb58b29f67f4 to your computer and use it in GitHub Desktop.
Write a function that takes a list of strings and returns the longest string that is a prefix of at least two strings in the list. longestCommonPrefix(["flower","flow","flight"]) -> "fl" longestCommonPrefix(["dog","racecar","car"]) -> "" longestCommonPrefix(["interstellar","internet","internal","interval"]) -> "inte"
import gleam/int
import gleam/io
import gleam/list
import gleam/string
pub fn chars_at_position(pos: Int, as_char: List(List(String))) {
// given a position, create a list of characters
list.map(as_char, fn(x) {
case { list.last(list.take(x, pos)) } {
Ok(val) -> val
_ -> ""
}
})
}
pub fn build(as_char: List(List(String)), min_length: Int) {
list.range(0, min_length)
|> list.map(fn(pos) { chars_at_position(pos + 1, as_char) })
}
pub fn longest_common_prefix(items: List(String)) -> String {
// convert the 1-d list into 2d list of characters
let as_char = list.map(items, string.to_graphemes)
// find the shortest length so that comparision can exit
let min_length =
list.map(as_char, list.length)
|> list.fold(1_000_000_000, fn(x, y) { int.min(x, y) })
let matches =
//Get a list of the character at each position to compare later
build(as_char, min_length)
// compare the returned character at the each position
|> list.filter(fn(x) { list.unique(x) |> list.length == 1 })
// Build the prefix
let prefix =
list.map(matches, fn(x) {
case { list.first(x) } {
Ok(val) -> val
_ -> ""
}
})
|> string.join("")
prefix
}
pub fn main() -> Nil {
list.each(
[
["flower", "flow", "flight"],
["dog", "racecar", "car"],
["interstellar", "internet", "internal", "interval"],
],
fn(items) {
echo items
let prefix = longest_common_prefix(items)
io.println(string.concat(["prefix:", " ", prefix]))
},
)
}
"""
Write a function that takes a list of strings and returns the longest string
that is a prefix of at least two strings in the list.
longestCommonPrefix(["flower","flow","flight"])
"fl"
longestCommonPrefix(["dog","racecar","car"])
""
longestCommonPrefix(["interstellar","internet","internal","interval"])
"inte"
"""
def longestCommonPrefix(items):
if not items:
return ""
if len(items) == 1:
return items[1]
longest, i = "", 0
prev = items[0][i]
while True:
prev, skip = items[0][i], False
for item in items[1:]:
if item[i] != prev:
skip = True
break
else:
longest += prev
i += 1
if skip:
break
return longest
print(longestCommonPrefix(["flower","flow","flight"]), "fl")
print(longestCommonPrefix(["dog","racecar","car"]), "")
print(longestCommonPrefix(["interstellar","internet","internal","interval"]), "inter")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment