はじめに
LeetCodeで解いた問題の実装方法についてまとめます。
最初は素直な探索により実装しましたが、入力された数字によってエラーが出たり出力結果が変わることから違う方法を試す必要がありました。
そこで、Rubyに用意されている配列のメソッドを調べながら、最終的に実装できるところまで試行錯誤しました。
今回は、その過程を備忘録としてまとめます。
前提
- AI：不使用
- 言語：Ruby
実装内容および問題について
今回取り組んだ問題は、LeetCodeの「Letter Combinations of a Phone Number」です。
電話の数字キーに対応する文字を使い、入力された数字列から考えられるすべての文字列を生成する問題です。
例えば、digits = "23" の場合、数字の2には["a", "b", "c"]が、数字の3には["d", "e", "f"]が対応しています。
それぞれの数字から1文字ずつ選び、すべての組み合わせを生成します。
1. まずは素直に実装してみる
最初は、eachとwhileを使って、数字に対応する文字配列を順番に取り出し、組み合わせを生成する方法を考えました。
考えていた手順は次のとおりです。
-
digitsの各桁から、対応する文字配列を取得 - 文字配列同士をループし、要素を組み合わせる
- 次の桁についても同様に処理する
- 最後まで処理したら、生成した組み合わせを返す
実際に書いたコードがこちらです。
def letter_combinations(digits)
numbers = {
"2" => ["a", "b", "c"],
"3" => ["d", "e", "f"],
"4" => ["g", "h", "i"],
"5" => ["j", "k", "l"],
"6" => ["m", "n", "o"],
"7" => ["p", "q", "r", "s"],
"8" => ["t", "u", "v"],
"9" => ["w", "x", "y", "z"]
}.freeze
return numbers[digits] if digits.length == 1
combinations = []
size = digits.length - 1
(0..size).each do |i|
prev = numbers[digits[i]]
while i != size
i += 1
after = numbers[digits[i]]
prev.each do |be|
after.each do |af|
combinations << be + af
end
end
end
end
combinations
end
しかし、この実装ではdigits = "234"のように3桁以上になると、3文字すべてを組み合わせた文字列を生成できません。
原因は、prevが最初に取得した文字配列のままになっていることです。
例えば、digits = "234"の場合、最初に取得した"2"の文字配列と、後続の"3"や"4"の文字配列を組み合わせています。
しかし、途中で生成した組み合わせを次の桁の処理に引き継いでいないため、3文字すべてを連結した文字列を生成できませんでした。
桁数が増えても対応できるように、組み合わせを生成する方法を考え直す必要がありました。
2. Rubyの組み合わせメソッドを調べる
別の方法がないか調べていたところ、組み合わせを生成できるメソッドにたどり着きました。
その中で試してみたのが、productメソッドです。
下記のように使用すると、各配列から1つずつ要素を選んだ組み合わせを生成できることがわかります。
p [1, 2].product([3, 4], [5, 6])
# -> [[1, 3, 5], [1, 3, 6], [1, 4, 5], [1, 4, 6], [2, 3, 5], [2, 3, 6], [2, 4, 5], [2, 4, 6]]
そして、次のように書くと、3つの配列からそれぞれ1要素ずつ選んだ組み合わせを生成できます。
digits = "234"の場合、27通りの組み合わせが得られます。
def letter_combinations(digits)
numbers = {
"2" => ["a", "b", "c"],
"3" => ["d", "e", "f"],
"4" => ["g", "h", "i"],
"5" => ["j", "k", "l"],
"6" => ["m", "n", "o"],
"7" => ["p", "q", "r", "s"],
"8" => ["t", "u", "v"],
"9" => ["w", "x", "y", "z"]
}
numbers[digits[0]].product(numbers[digits[1]], numbers[digits[2]])
end
p letter_combinations("234")
# -> [["a", "d", "g"], ["a", "d", "h"], ["a", "d", "i"], ["a", "e", "g"], ["a", "e", "h"], ["a", "e", "i"], ["a", "f", "g"], ["a", "f", "h"], ["a", "f", "i"], ["b", "d", "g"], ["b", "d", "h"], ["b", "d", "i"], ["b", "e", "g"], ["b", "e", "h"], ["b", "e", "i"], ["b", "f", "g"], ["b", "f", "h"], ["b", "f", "i"], ["c", "d", "g"], ["c", "d", "h"], ["c", "d", "i"], ["c", "e", "g"], ["c", "e", "h"], ["c", "e", "i"], ["c", "f", "g"], ["c", "f", "h"], ["c", "f", "i"]]
これなら、配列同士の組み合わせを自分で二重ループにして書く必要がありません。
ただし、配列を個別に指定しているため、入力の桁数が変わるたびにコードを変更する必要があります。
そこで、配列を動的に扱う方法を考えました。
3. 配列をまとめて展開する
まず、数字に対応する文字配列を別の配列に格納する方法を試しました。
head = [1, 2]
arr = []
arr << [3, 4]
arr << [5, 6]
p head.product(*arr).map{ | arr | arr.join }
# -> ["135", "136", "145", "146", "235", "236", "245", "246"]
ここで使っているのが、*arrです。
変数arrには[3, 4]と[5, 6]が格納されています。これを*arrで展開することで、productに複数の配列を引数として渡せます。
また、mapとjoinを使うことで、組み合わせの配列を文字列に変換しています。
この方法なら、配列の数が変わっても、個別に引数を指定する必要がありません。
これで、入力された数字の桁数に応じて組み合わせを生成できそうです。
4. 最終的なコード
ここまでの内容を組み合わせて、実装をまとめました。
def letter_combinations(digits)
numbers = {
"2" => ["a", "b", "c"],
"3" => ["d", "e", "f"],
"4" => ["g", "h", "i"],
"5" => ["j", "k", "l"],
"6" => ["m", "n", "o"],
"7" => ["p", "q", "r", "s"],
"8" => ["t", "u", "v"],
"9" => ["w", "x", "y", "z"]
}
# 文字列が1つならnumbersより返却して終了
return numbers[digits] if digits.length == 1
# 組み合わせを返す
arr = []
size = digits.length - 1
(1..size).each do |i|
prev = numbers[digits[i]]
arr << prev
end
head = numbers[digits[0]]
results = head.product(*arr)
results.map { |combination| combination.join }
end
最初に文字列が一つの場合を処理します。
その後、eachを使って1つ目以降の数字に対応する文字配列を取得し、arrに格納します。
最初の配列をheadとして取り出し、残りの配列を*arrで展開してproductに渡します。
最後に、生成した各組み合わせをjoinで文字列に変換して返します。
これで、入力された数字の桁数に応じて組み合わせを生成できるようになりました。
おわりに
今回の試行錯誤を通して、配列の組み合わせを生成する方法と、配列を引数として展開する方法を学べました。
今後もLeetCodeの問題を解く中で、実装につまずいた箇所や、解決するまでに考えたことを備忘録として残していきたいと思います。
参考