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

首先，这是我在几分钟内完成的，没有进行任何重构。所以我为混乱的代码道歉，我刚开始学习 Ruby 6 周前，所以请多多包涵！

所以最后我的问题是：我想知道这种方法的时间复杂度是多少。我的猜测是它会是 O(n^4) 因为第二个循环（对于四个字母的单词）嵌套了四次。虽然我不是很积极。所以我想知道这是否正确，以及是否有更好的方法来解决这个问题。

4

2 回答 2

0

这实际上是一个恒定时间算法，所以 O(1)（或者更明确地说，O(4^3 + 4^4)）

这是一个恒定时间算法的原因是，对于电话号码中的每个数字，您都在迭代一个固定数量（最多 4 个）可能的字母，这是事先已知的（这就是为什么您可以将hsh静态放入您的方法中） .

一种可能的优化是当您知道没有带有当前前缀的单词时停止搜索。例如，如果 3 位数字是“234”，您可以忽略所有以“bd”开头的字符串（有一些 bd 词，例如“bdellid”，但没有一个是 3 字母的，至少在我的/usr/share/dict/words）。

于 2012-04-19T00:57:43.893 回答
-1

从最初的措辞，我会假设这是请求所有的可能性，而不是作为输出的可能性的数量。

不幸的是，如果您需要返回每个组合，则无法将复杂性降低到指定键确定的复杂性以下。

如果它只是数字，它可能是恒定的时间。但是，要将它们全部打印出来，最终结果很大程度上取决于假设：

1）假设您要检查的所有单词都是由字母组成的，您只需要检查从2到9的八个键。如果不正确，只需在下面的函数中减去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 => []
}

在每个阶段，您只需检查下一步的可能性数量，并将每个可能的选择附加到字符串的末尾。如果你要这样做，那么最短时间将（基本上）是恒定时间（0，如果数字由全1和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 回答