ruby - 给定句子可以包含的分割数和单词，解扰字符串

Question

我正在解决一个问题，在这个问题中，我得到了一个已加扰的字符串。加扰是这样工作的。
原始字符串在随机位置和随机次数被切割成子字符串。
然后每个子串随机移动以形成一个新串。
我还得到了一个单词字典，这些单词可能是字符串中的单词。
最后，我得到了字符串中分割的次数。
我得到的例子是这样的:

dictionary = ["world", "hello"]
scrambled_string = rldhello wo
splits = 1

我的程序的预期输出将是原始字符串，在这种情况下:
“你好，世界”

Answer 1

假设初始字符串

"hello my name is Sean"

和

splits = 2

产量

["hel", "lo my name ", "is Sean"]

这三个部分被打乱以形成以下数组:

["lo my name ", "hel", "is Sean"]

然后将这个数组的元素连接起来形成:

scrambled = "lo my name helis Sean"

还假设:

dictionary = ["hello", "Sean", "the", "name", "of", "my", "cat", "is", "Sugar"]

先转换 dictionary到一组以加快查找速度。

require 'set'

dict_set = dictionary.to_set
  #=> #<Set: {"hello", "Sean", "the", "name", "of", "my", "cat", "is", "Sugar"}>

接下来我将创建一个辅助方法。

def indices_to_ranges(indices, last_index)
  [-1, *indices, last_index].each_cons(2).map { |i,j| i+1..j }
end

假设我们拆分 scrambled两次(因为 splits #=> 2 )，特别是在 'y' 之后和 'h' :

indices = [scrambled.index('y'), scrambled.index('h')]
  #=> [4, 11]

indices的第一个元素将永远是 -1最后一个值总是 scrambled.size-1 .
然后我们可以使用 indices_to_ranges将这些索引转换为 scrambed 中字符的索引范围:

ranges = indices_to_ranges(indices, scrambled.size-1)
  #=> [0..4, 5..11, 12..20]

a = ranges.map { |r| scrambled[r] }
  #=> ["lo my", " name h", "elis Sean"]

我们当然可以将这两个步骤结合起来:

a = indices_to_ranges(indices, scrambled.size-1).map { |r| scrambled[r] }
  #=> ["lo my", " name h", "elis Sean"]

接下来我将置换 a 的值.对于每个排列，我将连接元素以形成一个字符串，然后将字符串拆分为单个空格以形成一个单词数组。如果所有这些词都在字典中，我们可能会声称成功并完成了。否则，一个不同的数组 indices将被构造，我们再试一次，继续直到成功或所有可能的数组 indices已经考虑了。我们可以将所有这些放在下面的方法中。

def unscramble(scrambled, dict_set, splits)
  last_index = scrambled.size-1
  (0..scrambled.size-2).to_a.combination(splits).each do |indices|
    indices_to_ranges(indices, last_index).
    map { |r| scrambled[r] }.
    permutation.each do |arr|
      next if arr[0][0] == ' ' || arr[-1][-1] == ' '
      words = arr.join.split(' ')
      return words if words.all? { |word| dict_set.include?(word) }
    end
  end
end

让我们试试吧。

original string: "hello my name is Sean"
scrambled = "lo my name helis Sean"
splits = 4

unscramble(scrambled, dict_set, splits)
  #=> ["my", "name", "hello", "is", "Sean"]

见 Array#combination和 Array#permutation .