时间戳

首页 > 解决方案 > 如何检查字符串是否完全由相同的子字符串组成？

javascript - 如何检查字符串是否完全由相同的子字符串组成？

问题描述

我必须创建一个接受字符串的函数，它应该返回true或false基于输入是否包含重复的字符序列。给定字符串的长度总是大于1且字符序列必须至少有一次重复。

"aa" // true(entirely contains two strings "a")
"aaa" //true(entirely contains three string "a")
"abcabcabc" //true(entirely containas three strings "abc")

"aba" //false(At least there should be two same substrings and nothing more)
"ababa" //false("ab" exists twice but "a" is extra so false)

我创建了以下功能：

function check(str){
  if(!(str.length && str.length - 1)) return false;
  let temp = '';
  for(let i = 0;i<=str.length/2;i++){
    temp += str[i]
    //console.log(str.replace(new RegExp(temp,"g"),''))
    if(!str.replace(new RegExp(temp,"g"),'')) return true;
  }
  return false;
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

对此进行检查是真正问题的一部分。我买不起这样的低效解决方案。首先，它循环了一半的字符串。

第二个问题是它replace()在每个循环中使用，这使得它变慢。关于性能有更好的解决方案吗？

标签： javascriptstringalgorithm

解决方案

关于这样的字符串有一个漂亮的小定理。

一个字符串由重复多次的相同模式组成，当且仅当该字符串是其自身的非平凡旋转。

在这里，旋转意味着从字符串的前面删除一些字符并将它们移到后面。例如，hello可以旋转字符串以形成以下任何字符串：

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell

要了解为什么会这样，首先，假设一个字符串由字符串 w 的 k 个重复副本组成。然后从字符串的前面删除重复模式 (w) 的第一个副本并将其粘贴到后面将返回相同的字符串。证明相反的方向有点棘手，但想法是，如果您旋转一个字符串并恢复您开始时的状态，您可以重复应用该旋转以使用相同模式的多个副本平铺字符串（该模式是您需要移动到最后进行旋转的字符串）。

现在的问题是如何检查是否是这种情况。为此，我们可以使用另一个美丽的定理：

如果 x 和 y 是长度相同的字符串，则当且仅当 x 是 yy 的子字符串时，x 是 y 的旋转。

作为一个例子，我们可以看到这lohel是一个hello如下的旋转：

hellohello
   ^^^^^

在我们的例子中，我们知道每个字符串 x 将始终是 xx 的子字符串（它会出现两次，在 x 的每个副本中出现一次）。所以基本上我们只需要检查我们的字符串 x 是否是 xx 的子字符串，而不允许它在第一个或中间字符匹配。这是一个单线：

function check(str) {
    return (str + str).indexOf(str, 1) !== str.length;
}

假设indexOf使用快速字符串匹配算法实现，这将在 O(n) 时间内运行，其中 n 是输入字符串的长度。

希望这可以帮助！

推荐阅读