1

これは宿題ではなく、ウェブ上で見つけた面接の質問で、面白そうです。

だから私は最初にこれを見てみました：電話の文章題-しかし、それは不十分な言葉遣い/いくつかの論争を引き起こしたようです。私の質問は、その背後にある時間の複雑さに関するものであることを除いて、ほとんど同じです。

入力として10桁の電話番号を指定した場合に、考えられるすべての単語をリストします。これが私がしたことです：`

def main(telephone_string)
  hsh = {1 => "1", 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"], 0 => "0" }
  telephone_array = telephone_string.split("-")
  three_number_string = telephone_array[1]
  four_number_string = telephone_array[2]
  string = ""
  result_array = []
  hsh[three_number_string[0].to_i].each do |letter|
    hsh[three_number_string[1].to_i].each do |second_letter|
      string = letter + second_letter
      hsh[three_number_string[2].to_i].each do |third_letter|
        new_string = string + third_letter
        result_array << new_string
      end
    end 
  end

  second_string = ""
  second_result = []
  hsh[four_number_string[0].to_i].each do |letter|
    hsh[four_number_string[1].to_i].each do |second_letter|
      second_string = letter + second_letter
      hsh[four_number_string[2].to_i].each do |third_letter|
        new_string = second_string + third_letter
        hsh[four_number_string[3].to_i].each do |fourth_letter|
          last_string = new_string + fourth_letter
          second_result << last_string
        end
      end
   end
end
  puts result_array.inspect
  puts second_result.inspect
end

まず、これは私が数分で一緒にハッキングしたものであり、リファクタリングは行われていません。コードが乱雑になったことをお詫びします。6週間前にRubyを学び始めたばかりですので、ご容赦ください。

最後に、私の質問です。この方法の時間計算量はどうなるのだろうかと思っていました。2番目のループ（4文字の単語の場合）は4回ネストされているため、O（n ^ 4）になると思います。しかし、私は本当に前向きではありません。それで、それが正しいかどうか、そしてこの問題を解決するためのより良い方法があるかどうかを知りたいと思います。

4

2 に答える 2

0

これは実際には定数時間アルゴリズムなので、O(1) (より明確に言えば O(4^3 + 4^4))

これが定数時間アルゴリズムである理由は、電話番号の各桁に対して、事前にわかっている固定数 (最大 4) の可能な文字を反復しているためです (これがhsh、メソッドに静的に入れることができる理由です)。 .

考えられる最適化の 1 つは、現在のプレフィックスを持つ単語がないことがわかっている場合に検索を停止することです。たとえば、3 桁の数字が「234」の場合、「bd」で始まるすべての文字列を無視できます (「bdellid」などの bd 単語はいくつかありますが、3 文字の単語はありません。少なくとも私の場合は/usr/share/dict/words)。

于 2012-04-19T00:57:43.893 に答える
-1

元の言い回しから、出力として可能性の数ではなく、すべての可能性を要求していると思います。

残念ながら、すべての組み合わせを返す必要がある場合、指定されたキーによって決定される複雑さを下げる方法はありません。

単純な数字なら、一定の時間である可能性があります。ただし、それらをすべて印刷するには、最終結果は仮定に大きく依存します。

1) チェックしているすべての単語が文字だけで構成されていると仮定すると、2 から 9 までの 8 つのキーに対してチェックするだけで済みます。これが正しくない場合は、以下の関数で 8 を代入してください。

2) すべてのキーのレイアウトがここで設定したとおり (オクトソープやアスタリスクなし) であり、空の配列の内容が最後の単語でスペースを占有しないと仮定します。

{
  1 => [],
  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"],
  0 => []
}

各段階で、次のステップの可能性の数を確認し、可能性のある各選択肢を文字列の末尾に追加するだけです。そうする場合、最小時間は (本質的に) 一定時間 (数値がすべて 1 と 0 で構成される場合は 0) になります。ただし、関数は O(4^n) となり、n は 10 で最大になります。組み合わせの最大可能数は、毎回 7 または 9 に達する場合、4^10 になります。

コードに関しては、いくつかの基本的なネストされたループを含む単一のループをお勧めします。これはRubyのコードです。実行していませんが、構文エラーがある可能性があります。

def get_words(number_string)
  hsh = {"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"]}

  possible_array =  hsh.keys
  number_array = number_string.split("").reject{|x| possible_array.include?(x)}

  if number_array.length > 0
    array = hsh[number_array[0]]
  end

  unless number_array[1,-1].nil?
        number_array.each do |digit|
            new_array = Array.new()
            array.each do |combo|
                hsh[digit].each do |new|
                new_array = new_array + [combo + new]
            end
        end
        array = new_array
    end
    new_array
end
于 2014-03-20T23:05:05.817 に答える