Last active
May 5, 2025 21:51
-
-
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"
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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])) | |
}, | |
) | |
} |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
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