数字で綴られた単語を見つけるアルゴリズム

StackOverflow https://stackoverflow.com/questions/1628123

  •  06-07-2019
  •  | 
  •  

質問

アルファベットから値へのマッピングを前提として、特定の数字で綴られる可能性のあるすべての単語を決定する方法を見つけようとしています。

最終的に、文字の1桁または2桁の値のマッピングに有効なソリューションを見つけたいと思いますが、説明のために、A = 1、B = 2、... Z = 26と仮定します。

例： 12322 は、 abcbb（1,2,3,2,2）、 lcbb（12,3,2,2）と同じにすることができます、 awbb（1,23,2,2）、 abcv（1,2,3,22）、 awv（1,23、 22）、または lcv（12,3,22）。

これまで私が考えてきたことは次のとおりです。

数字を使用して、考えられるすべての単語のツリーを構築します。

これを行うには、ダミーデータを持つ1つのルートノードを持つツリーから始めます。

次に、最下位桁から数字を1桁ずつ解析します。

各ステップで、番号の残りの部分の最後の桁を取得し、それを現在のノードの左のサブツリーに挿入し、そのノードの左のサブツリーの番号からその桁を削除します。同じノードについて、前の2つの数字が一緒に有効なアルファベットを形成しているかどうかを確認し、そうであれば、それらを正しいサブツリーに配置します（そして、そのノードの右サブツリーの番号から2桁を削除します）。

次に、残りの数字がなくなるまで、残っている数字の部分を使用して、各ノードに対して上記の手順を再帰的に繰り返します。

説明のため、 12322 の場合、ツリーは次のようになります。

                *
             /     \
            /       \
           2         22
         /         /   \
        2         3     23
      /   \      / \    /
    3      23   2   12 1
   / \    /    /
  2   12 1    1
 /
1

単語を取得するには、葉からノードまでの可能なすべてのパスを走査します。

これは、私がかなり単純な問題だと思っていたものに対する過度に複雑なソリューションのようです。これを解決する簡単な方法があるかどうかを見つけようとしています。

役に立ちましたか？

解決

[2、3、2、2] の可能な組み合わせをすべて持っているとします。 [1、2、3、2、2] （ [1] を頭に追加）？推測するのは難しくありません：

  A1: put [1] to the head of all_the_combinations_of[1,2,3,2,2] and 
  A2: put [1*10 + 2] to the head of all_the_combinations_of[2,3,2,2] if [1*10 + 2 <=26]

これを取得したら、次の手順は簡単です。参考のために、recusion traceを使用してRubyバージョンを実装しました。

def comb a
    c = []
    puts a.inspect
    return [a] if a.length <= 1

    c =  comb(a[1..-1]).map {|e| [a[0]] + e}
    if a[0] * 10 + a[1] <= 26
            c += comb(a[2..-1]).map { |f| [a[0] * 10 + a[1]] + f }
    end
    c
end

h = Hash[*(1..26).to_a.zip(('A'..'Z').to_a).flatten]
#h.keys.sort.each {|k| puts "#{k}=>#{h[k]}"}

comb([1,2,3,2,2]).each do |comb|
    puts comb.map {|k| h[k]}.join
end

[1, 2, 3, 2, 2]
  A1 [2, 3, 2, 2]
      [3, 2, 2]
         [2, 2]
            [2]
             []
      [2, 2]
         [2]
          []
  A2 [3, 2, 2]
      [2, 2]
         [2]
          []
ABCBB
ABCV
AWBB
AWV
LCBB
LCV

他のヒント

実際にツリーを構築する必要はありません-再帰するだけです：

  1. 1桁を取得します。単語をそれ自体が文字とみなして単語を形成できるかどうかを確認し、再帰します。
  2. 再帰から戻ったときに、別の数字を追加して（以前に1または2だった場合）、再度再帰してみてください。

ブルートフォースソリューションは、1〜Nの配列を動的に埋めることです。 a [i] 要素には、 a [1] a [2 ] a [3] ... a [i] 展開後。ストレッチからa [1]を埋めてから、 a [1] セットと文字列の2番目の文字に基づいて a [2] を埋めることができます。次に、a [3]などを入力します。各ステッドで、 a [i-1] および a [i-2] （および s [i-1] および s [i] 、ここで s は数字のシーケンスです。）

最後に、 a [n] に入力すると、回答が含まれます。

例 '12322'の場合、シーケンスは次のようになります。

a[1] = { "a" }
a[2] = { a + 'b' | a in a[1] } union { "l" } = { "ab", "l" }
a[3] = { a + 'c' | a in a[2] } union { a + 'w' | a in a[1] } = { "abc", "lc", "aw" }
a[4] = { a + 'b' | a in a[3] } union { } = { "abcb", "lcb", "awb" }
a[5] = { a + 'b' | a in a[4] } union { a + 'v' | a in a[3] } = { "abcbb", "lcbb", "awbb", "abcv", "lcv", "awv" }

これは、本質的に上記の再帰的ソリューションの動的プログラミングバージョンです。

これを行う別の方法は、問題を逆にすることです：

  • 単語の辞書が与えられ、生成される数値文字列を計算し、このデータをマップ/辞書構造、つまりtable ['85 '] =' hi 'に保存します
  • 検索する数値の最初のx桁ごとに、テーブルにあるかどうかを確認します。つまり、table.ContainsKey（ '1'）、table.ContainsKey（'12 '）、...
  • 単語シーケンスを検索しようとしている場合は、数値文字列の各位置から始まる単語を生成し、再帰検索を実行して、その中のすべてのフレーズを検索します。
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top