在 Elixir 中求解 "first unique character in a string"

Question

我正在尝试解决 Elixir 中的 LeetCode 问题，因为没有大量资源用于该语言的代码审查（尽管这可能会改变或者我可能是错的）并且因为我来自 OOP 背景我我想我会继续 post 这里。

我正在尝试使用 Elixir 解决 "first unique character in a string" LeetCode 问题，发现我的解决方案比我想象的更复杂，因为我不知道 Elixir 中的 Maps 会自动拥有它们的密钥按字母顺序排序而不是按插入排序（尽管我可能错了）。

我很想听听任何 cleaner/more 接受的解决方案。 FWIW，我打算把它们写在最后，这样其他人就可以找到如何解决我自己找不到的问题的例子。

Given a string, find the first non-repeating character in it and return its index. If it doesn't exist, return -1.

Examples:

s = "leetcode"
return 0.

s = "loveleetcode"
return 2.
 

Note: You may assume the string contains only lowercase English letters.

defmodule Algos do
  def first_unique_char_index(str) do
    
    arr = String.split(str, "", trim: true)
    indexes = Enum.with_index(arr)

    first = Enum.frequencies(arr)
    |> Map.to_list
    |> Enum.sort(fn ({a,_b}, {c,_d}) -> 
      {_char1, i1} = Enum.find(indexes, (fn {x,_i} -> x == a end)) 
      {_char2, i2} = Enum.find(indexes, (fn {y,_j} -> y == c end))
      i1 <= i2 
      end)
    |> Enum.find(fn {_char, num} -> num == 1 end)

    case first do
      {char, _num} ->
        result = Enum.find(indexes, fn {x, _i} -> char == x end)
        {_letter, index} = result
        index
      nil ->
        -1
    end

  end

end

Algos.first_unique_char_index("aabcc") # returns 2
Algos.first_unique_char_index("picadillo") # returns 0
Algos.first_unique_char_index("dood") # returns -1

Answer 1

这是一个很好的小谜题，可以通过几个累加器来解决。您可以使用内部二进制表示而不是拆分字符串，或者（为了跳过编码所涉及的额外复杂性）您可以将字符串转换为字符列表并专注于整数部分。

这是一个可能的解决方案（未经过彻底测试）：

defmodule FirstUniq do
  def char(string) do
    [first_char | rest] = to_charlist(string)
    eval_char(first_char, 0, rest, rest)
  end

  # Case where we hit the end of the string without a duplicate!
  defp eval_char(_char, index, [], _), do: index

  # Case where a character repeats... increment the index and eval next char
  defp eval_char(char, index, [x | _], [next_char | rest]) when char == x do
    eval_char(next_char, index + 1, rest, rest)
  end

  # Case where the character does not repeat: keep looking
  defp eval_char(char, index, [x | rest], acc2) when char != x do
    eval_char(char, index, rest, acc2)
  end
end

# should be 0 (because "l" does not occur more than once)
IO.puts(FirstUniq.char("leetcode"))

# should be 2 (because "v" is the first char that does not repeat)
IO.puts(FirstUniq.char("loveleetcode"))

艰苦的工作是由 eval_char/4 函数完成的，其多个子句的作用类似于 case 语句。诀窍是我们必须保留两个累加器，这类似于嵌套循环。

我建议 Exercism's Elixir Track 展示您将在该语言中遇到的许多常见模式。

Answer 2

以下可能是最高效的解决方案；我决定把它放在这里，因为它揭示了几个有趣的技巧。

"leetcode"
|> to_charlist()
|> Enum.with_index() # we need index to compare by
|> Enum.reduce(%{}, fn {e, i}, acc ->
  # trick for the future: `:many > idx` for any integer `idx` :)
  Map.update(acc, e, {e, i}, &{elem(&1, 0), :many})
end)
|> Enum.sort_by(&elem(elem(&1, 1), 1)) # sort to get a head
|> case do
  [{_, {_, :many}} | _] -> "All dups"
  [{_, {result, index}} | _] -> {<<result>>, index}
  _ -> "Empty input"
end
#⇒ {"l", 0}

在 Elixir 中求解 "first unique character in a string"

Solving "first unique character in a string" in Elixir

algorithm

functional-programming

elixir