ruby - 给定句子可包含的分割数和单词数，对字符串进行打乱

Question

我正在解决一个问题，其中给我一个已被扰乱的字符串。加扰的工作原理如下。

原始字符串被切成随机位置和随机次数的子字符串。 然后随机移动每个子字符串以形成新字符串。

我还获得了一个字典，其中包含字符串中可能出现的单词。

最后，我得到了字符串中的分割数。

我得到的例子是这样的:

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

我的程序的预期输出将是原始字符串，在本例中: “ Hello World ”

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"]

首先将字典转换为集合以加快查找速度。

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 分割两次(因为 分割 #=> 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 .