Elixir 找到字符串中最长的子串
Elixir find the longest substring in a string
我的问题和Find the longest substring in a string
一模一样
但与丹药有关
我目前的实现非常丑陋:
str = "aabbbssssssggssrrrr"
String.split(str, "") |> Enum.chunk_while([], fn elem, acc ->
cond do
(length(acc) == 0) ->
{:cont, [elem]}
(acc == [""]) ->
{:cont, [elem]}
(List.last(acc) == elem) ->
{:cont, [elem | acc]}
true ->
{:cont, Enum.reverse(acc), []}
end
end,
fn
[] -> {:cont, []}
acc -> {:cont, Enum.reverse(acc), []}
end) |> Enum.map(fn e -> Enum.reduce(e, "", &<>/2) end) |> Enum.max_by(&String.length/1)
是否可以像 ruby 那样写一行或至少更短一些?
带块的链接 ruby 解决方案非常差。它执行几个绝对不需要的操作,如拆分、连接等,这可能会大大降低长输入的性能。
最简单的方法是使用带有 back reference.
的正则表达式
str = "aabbbssssssggssrrrr"
Regex.scan(~r/(.){1,}/, str, capture: :first)
#⇒ [["aa"], ["bbb"], ["ssssss"], ["gg"], ["ss"], ["rrrr"]]
现在如何获得最长的字符串是一个偏好问题,例如:
~r/(.){1,}/
|> Regex.scan(str, capture: :first)
|> Enum.sort_by(&-String.length(hd(&1)))
|> hd()
|> hd()
#⇒ "ssssss"
或者,List.flatten/1
~r/(.){1,}/
|> Regex.scan(str, capture: :first)
|> List.flatten()
|> Enum.sort_by(&-String.length(&1))
|> hd()
#⇒ "ssssss"
最灵丹妙药的解决方案是使用Enum.reduce/3
,这样O(N)
只需要一次输入。
"aabbbssssssggssrrrr"
|> to_charlist()
|> Enum.reduce(%{char: ??, curr: 0, max: []}, fn
ch, %{char: ch, max: max, curr: curr} when curr < length(max) ->
%{char: ch, max: max, curr: curr + 1}
ch, %{char: ch, curr: curr} ->
%{char: ch, max: List.duplicate([ch], curr + 1), curr: curr + 1}
ch, %{max: max} ->
%{char: ch, max: max, curr: 1}
end)
|> Map.get(:max)
|> Enum.join()
#⇒ "ssssss"
我的问题和Find the longest substring in a string
一模一样但与丹药有关
我目前的实现非常丑陋:
str = "aabbbssssssggssrrrr"
String.split(str, "") |> Enum.chunk_while([], fn elem, acc ->
cond do
(length(acc) == 0) ->
{:cont, [elem]}
(acc == [""]) ->
{:cont, [elem]}
(List.last(acc) == elem) ->
{:cont, [elem | acc]}
true ->
{:cont, Enum.reverse(acc), []}
end
end,
fn
[] -> {:cont, []}
acc -> {:cont, Enum.reverse(acc), []}
end) |> Enum.map(fn e -> Enum.reduce(e, "", &<>/2) end) |> Enum.max_by(&String.length/1)
是否可以像 ruby 那样写一行或至少更短一些?
带块的链接 ruby 解决方案非常差。它执行几个绝对不需要的操作,如拆分、连接等,这可能会大大降低长输入的性能。
最简单的方法是使用带有 back reference.
的正则表达式str = "aabbbssssssggssrrrr"
Regex.scan(~r/(.){1,}/, str, capture: :first)
#⇒ [["aa"], ["bbb"], ["ssssss"], ["gg"], ["ss"], ["rrrr"]]
现在如何获得最长的字符串是一个偏好问题,例如:
~r/(.){1,}/
|> Regex.scan(str, capture: :first)
|> Enum.sort_by(&-String.length(hd(&1)))
|> hd()
|> hd()
#⇒ "ssssss"
或者,List.flatten/1
~r/(.){1,}/
|> Regex.scan(str, capture: :first)
|> List.flatten()
|> Enum.sort_by(&-String.length(&1))
|> hd()
#⇒ "ssssss"
最灵丹妙药的解决方案是使用Enum.reduce/3
,这样O(N)
只需要一次输入。
"aabbbssssssggssrrrr"
|> to_charlist()
|> Enum.reduce(%{char: ??, curr: 0, max: []}, fn
ch, %{char: ch, max: max, curr: curr} when curr < length(max) ->
%{char: ch, max: max, curr: curr + 1}
ch, %{char: ch, curr: curr} ->
%{char: ch, max: List.duplicate([ch], curr + 1), curr: curr + 1}
ch, %{max: max} ->
%{char: ch, max: max, curr: 1}
end)
|> Map.get(:max)
|> Enum.join()
#⇒ "ssssss"