RubyでBacktracking

いつものようにLeetCodeをやっていると、解法としてBacktrackingというものが出てきた。アルゴリズムの名前らしい。

leetcode.com

Backtrackingとはなんだろうか。

問題

まず解くべき問題を説明する。

2-9の数字からなる文字列が与えられる。それぞれの数字は、以下の画像のように文字列の組み合わせを持っている。

与えられた数字をそれぞれの文字列に変換した場合にできうる文字列をすべて答えよ、という問題。

電話のキー （https://leetcode.com/problems/letter-combinations-of-a-phone-number/ より）

例：

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

※ 例では辞書順の出力になっているが、順序は問わない

ツリー構造

組み合わせを洗い出すと、こんなツリー構造になる。

ツリー構造

これらすべての要素を列挙する解法の1つがBacktrackingということらしい。

Backtrackingとはなにか

概念

こちらの説明を読んでみる。

Backtracking is an algorithm for finding all solutions by exploring all potential candidates. If the solution candidate turns to be not a solution (or at least not the last one), backtracking algorithm discards it by making some changes on the previous step, i.e. backtracks and then try again.

具体的には

backtrack(combination, next_digits)という関数を考える。 combinationは現在の文字列(an ongoing letter combination)で、next_digitsは残りの数字(the next digits to check)である。

洗い出しの過程（https://leetcode.com/problems/letter-combinations-of-a-phone-number/solution/ より）

この関数は以下の処理を行う。

• If there is no more digits to check that means that the current combination is done.
• If there are still digits to check :
  • Iterate over the letters mapping the next available digit.
    • Append the current letter to the current combination combination = combination + letter.
    • Proceed to check next digits : backtrack(combination + letter, next_digits[1:]).

つまり、

• next_digitsが空の配列ならば、そのcombinationの処理は終わり
• next_digitsが空じゃなければ、
  • 次の数字の持つ文字列に対して繰り返し処理を行う
    • 文字列をcombinationに追加する combination = combination + letter
    • 次の数字に進む backtrack(combination + letter, next_digits[1..-1]

Rubyで書いてみる

# @param {String} digits
# @return {String[]}
def letter_combinations(digits)
    return [] if digits.empty?
    @result = []
    @digit_to_letters = {
        '2' => %w[a b c],
        '3' => %w[d e f],
        '4' => %w[g h i],
        '5' => %w[j k l],
        '6' => %w[m n o],
        '7' => %w[p q r s],
        '8' => %w[t u v],
        '9' => %w[w x y z],
    }
    backtrack('', digits)
    @result
end

private

def backtrack(combination, next_digits)
    if next_digits.empty?
        @result << combination
        return
    else 
        @digit_to_letters[next_digits[0]].each do |letter|
            backtrack(combination + letter, next_digits[1..-1])
        end
    end 
end

コメントをつけるとこうなる。

# @param {String} digits
# @return {String[]}
def letter_combinations(digits)
    return [] if digits.empty?
    @result = []
    @digit_to_letters = {
        '2' => %w[a b c],
        '3' => %w[d e f],
        '4' => %w[g h i],
        '5' => %w[j k l],
        '6' => %w[m n o],
        '7' => %w[p q r s],
        '8' => %w[t u v],
        '9' => %w[w x y z],
    }
    backtrack('', digits)
    @result
end

private

def backtrack(combination, next_digits)
    # next_digitsが空の配列ならば、
    if next_digits.empty?
        # もう子要素はないので、現時点での文字列を追加して処理を終える
        @result << combination
        return
    # next_digitsが空じゃなければ、
    else 
        # 次の数字が持つ文字列セットの要素1つずつに対して
        @digit_to_letters[next_digits[0]].each do |letter|
            # backtrack関数を呼び出す
            backtrack(combination + letter, next_digits[1..-1])
        end
    end 
end

こういう再帰系の処理は慣れが必要な感がある。精進あるのみ。

参考

leetcode.com