ruby - 使用 Ruby 查找给定编码字符串的组合

Question

我在一次面试中被问到这个问题，我想不出一个令人满意的解决方案。如果有人可以提供一些指示，我们将不胜感激。

给定一个像这样的映射

  mapping = {"A" => 1, "B" => 2, "C" => 3..... "Z" => 26}

 encode("A") == "1"
 encode("BA") == "21"
 encode("ABC") == "123"
 encode("") == ""


decode("1") == ["A"] -> 1
decode("21") == ["BA", "V"] -> 2
decode("123") == ["ABC", "JC", "AX"] -> 3
decode("012") == [] -> 0
decode("") == [""] -> 1
decode("102") == ["JB"] -> 1


numDecode(X) == len(decode(X))
numDecode("1") == 1
numDecode("21") == 2
numDecode("123") == 3
numDecode("") == 1
numDecode("102") == 1
numDecode("012") == 0

我们需要一个 numDecode 方法来给出唯一解数组的长度。

更新:

给定如下映射:

mapping = {"A" => 1, "B" => 2, "C" => 3..... "Z" => 26}

Suppose we are given a string as "A" the it can be encoded as : "1"

encode("A") should return "1"
encode("BA") should return "21" as if mapping is a hash then B has a value of 2, A has a value of 1.
encode("ABC") should return "123" as mapping["A" is 1, mapping["B"] is 2, and mapping["C"] is 3.
encode("") should return "" as it is not in mapping.


Now if decode("1") is called then it should return an array with one element i.e. ["A"] as key matching with 1 as value in mapping is "A".
decode("") should return an array with empty string i.e. [""].
decode("21") should return an array ["BA", "U"] as 2 is "B", 1 is "A" and "U" is 21 in mapping.
decode("012") should return an empty array as string starts with "0" which is not in mapping keys.
decode("102") should return an array as ["JB"] as "10" is J and "2" is B.

最后 numDecode 应该返回数组中唯一解码字符串的计数。所以，

numDecode(X) == len(decode(X))
numDecode("1") == 1
numDecode("21") == 2
numDecode("123") == 3
numDecode("") == 1
numDecode("102") == 1
numDecode("012") == 0

Answer 1

这是一个有趣的问题，与之配套的面试技巧最有可能看到批判性思维的程度。一个好的面试官可能不会期待一个单一的标准正确答案。

如果你得到一个递归的 decode 解决方案然后列举，那么你在我看来做得很好(至少我会雇用大多数能够在面试中通过一段递归代码展示清晰思考的候选人!)

话虽如此，一个关键提示是问题要求 num_decode 函数，不一定是 encode 和 decode 的实现。

可以通过分析排列组合获得更深入的理解和结构。它允许您编写一个 num_decode 函数，该函数可以处理具有数百万个可能答案的长字符串，而无需填满内存或花费数小时来枚举所有可能性。

首先请注意，任何一组单独的歧义编码都会增加整个字符串的可能性数量:

1920 -> 19 is ambiguous 'AI' or 'S' -> 'AIT' or 'ST'

192011 -> 11 is also ambiguous 'AA' or 'K' -> 'AITAA', 'AITK', 'STAA', 'STK'

这里19有两种可能的解释，11也有两种。具有这两个独立的歧义编码实例的字符串具有 2 * 2 == 4 有效组合。

歧义编码的每个独立部分都将整个解码值集的大小乘以它所代表的可能性的数量。

接下来如何处理较长的歧义部分。当您将一个不明确的数字添加到一个不明确的序列中时会发生什么:

11 -> 'AA' or 'K' -> 2
111 -> 'AAA', 'AK', 'KA' -> 3
1111 -> 'AAAA', 'AAK', 'AKA', 'KAA', 'KK' -> 5
11111 -> 'AAAAA', 'AAAK', 'AAKA', 'AKAA', 'AKK', 'KAAA', 'KAK', 'KKA' -> 8

2,3,5,8应该很眼熟吧，就是斐波那契数列，这是怎么回事？答案是向序列中添加一个数字允许所有先前的组合加上之前的子序列的组合。通过将数字 1 添加到序列 1111 中，您可以将其解释为 1111(1) 或 111(11) - 因此您可以将 1111 和 111 中的可能性数量相加以获得 11111 中的可能性数量。也就是说，N(i) = N(i-1) + N(i-2) 这就是斐波那契数列的构造方式。

因此，如果我们能够检测出不明确的编码序列并获得它们的长度，我们现在就可以计算出可能的解码次数，无需实际进行解码:

# A caching Fibonacci sequence generator
def fib n
  @fibcache ||= []
  return @fibcache[n] if @fibcache[n]
  a = b = 1
  n.times do |i|
    a, b = b, a + b
    @fibcache[i+1] = a
  end
  @fibcache[n]
end

def num_decode encoded
  # Check that we don't have invalid sequences, raising here, but you 
  # could technically return 0 and be correct according to question
  if encoded.match(/[^0-9]/) || encoded.match(/(?<![12])0/)
    raise ArgumentError, "Not a valid encoded sequence"
  end

  # The look-ahead assertion ensures we don't match
  # a '1' or '2' that is needed by a '10' or '20'
  ambiguous = encoded.scan(/[12]*1[789]|[12]+[123456](?![0])/)

  ambiguous.inject(1) { |n,s| n * fib(s.length) }
end

# A few examples:
num_decode('')  # => 1
num_decode('1') # => 1
num_decode('12') # => 2
num_decode('120') # => 1
num_decode('12121212') # => 34
num_decode('1212121212121212121212121211212121212121') # => 165580141

它是相对较短的字符串，如 foil 尝试枚举的最后一个字符串直接通过解码的可能性。

scan 中的正则表达式经过一些实验才正确。在 7 之后添加 8 、 9 或 1 是不明确的，但在 2 之后则不然。您还希望避免将 1 或 2 直接计数在 0 之前作为模糊序列的一部分，因为 10 或 20 没有其他解释。我认为在确定当前版本之前，我对正则表达式进行了大约十二次尝试(我认为这是正确的，但我在测试第一个版本的大多数时候确实一直在寻找异常(exception)以更正值)。

最后，作为练习，应该可以使用此代码作为编写解码器的基础，该解码器直接输出第 N 种可能的解码(或者甚至是从任何起点懒惰地枚举它们，而不需要过多内存的解码器)或 CPU 时间)。