删除相邻重复的子字符串

Question

我试图移除长度为k的重复相邻子字符串，其中k指的是单词数量。代码应该以递归方式开始，从到。

例如，

“i sat down to write an article an article this morning but found that i i could make no progress”

将变成

“i sat down to write an article this morning but found that i could make no progress”。

我如何实现这一点？ 我可以通过以下方法实现删除长度为1的相邻子字符串：

str.chunk{|n| n}.map(&:first)

- Rajat Suneja

---

这是一个非常复杂（通常无法解决）的任务，值得一篇博士论文而不是一个 Stack Overflow 的问题。首先：从“我喜欢移动它，移动它，我喜欢移动它，移动它”中应该删除什么？ - Aleksei Matiushkin

在这种情况下，它应该递归地工作，即：第一次迭代 -“我喜欢动它动它”第二次迭代 -“我喜欢动它” - Rajat Suneja

你的问题不够清晰。要移除子字符串“an article”，k 应该是11。要移除子字符串“i”，k 应该是2。那么，移除它们的逻辑是什么呢？ - sawa

@sawa - 这里的 'k' 指的是一个单词而不是字符，并且它以递归方式工作，因此 'k' 从1开始，一直到字符串中单词数的长度。 - Rajat Suneja

你在问题中完全没有提到这一点。请详细说明所有细节，以使你的问题更易理解。 - sawa

谢谢sawa，已经更新了问题。 - Rajat Suneja

Answer 1

s = "i sat down to write an article an article this morning but found that i i could make no progress"

max = s.scan(/\S+/).length
# => 20
1.upto(max).each_with_object(s) do
  |n, s| s.gsub!(/((?:\b\s*\S+){#{n}})\1/, '\1')
end
# => "i sat down to write an article this morning but found that i could make no progress"

顺便说一下，

"I like to move it move it, I like to move it move it"

会导致：

"I like to move it, I like to move it"

注意：

"I like to move it"

正如您在评论中提到的那样，因为上述字符串中没有相邻的重复（请注意逗号和空格），所以需要这样做。

- sawa

---

很好。如果您能更详细地解释一下正则表达式在您的代码中是如何工作的，那就太棒了。 - Mohamad

s.gsub(/((?:\b\s*\S+)+)\1/, '\1') 在不需要迭代的情况下运行良好。 - Rajat Suneja

Rajat，'a a b a a b'.gsub(/((?:\b\s*\S+)+)\1/, '\1') => "a a b a b"，而期望的是 "a b"。 - Cary Swoveland

你的代码显然曾经是有效的，但显然在执行过程中出现了一些问题。现在它返回原始字符串。 - Cary Swoveland

我在某个时候意识到了这个问题，但直到现在才有权限进入这里。这是由于没有使用插值语法而导致的 n 问题。我已经修复了它。对此很抱歉。 - sawa

Answer 2

我假设字符串中除了空格以外没有任何其他的空白符（如制表符、换行符、回车符等），单词之间只有一个空格分隔，如果由多个空格分隔，则返回的字符串只包含单词间的一个空格。（对于后者有一种解决方法，但它不是问题的核心所在。）

def remove_repeats(str)
  s = str.squeeze(' ')
  s.insert(0, ' ')
  change = ''
  until change.nil?
    change = s.gsub!(/(?:((?: \S+)+))\1/, '\1')
  end
  s[1..-1]
end

remove_repeats 'a a b a a b'              #=> "a b"
remove_repeats 'a a b c a a b c d'        #=> "a b c d"
remove_repeats ' c a a b a a b d a a b e' #=> " c a b d a b e"
remove_repeats 'aa a bb bb b'             #=> "aa a bb b"
remove_repeats 'a b c d e f'              #=> "a b c d e f"
remove_repeats ''                         #=> ""

正则表达式的解读如下：“针对由一个空格后跟非空格字符串组成的任意字符串，重复该字符串一次或多次，并将结果保存在捕获组1中。匹配捕获组内容一次或多次，然后匹配捕获组内容。如果gsub！至少进行了一次替换，则更新s；否则，gsub！返回nil。请注意，在替换文本之前，我在字符串开头插入了一个空格，然后在完成所有替换之后将其删除。”

“/((?: \S+)+)\1/”也适用于上述示例，但可能需要更多迭代才能获得解决方案。

我无法证明这在所有情况下都有效。我邀请读者提供证明或反例。

- Cary Swoveland