2

我想尝试创建一个算法来删除字符串中的重复字符串。

例如

输入：Hello 输出：Helo

输入：AAAAZZZZ5 输出：AZ5

输入：“苹果、苹果和橙子” 输出：“苹果和橙子”

我写了下面的算法（JSFiddle here）

function removeRepeat(str)
{
    var index = 0;
    var tempS = str.length;
    var currentBuffer = "";
    var repeatCharIndex = 1;
    console.log(str);
    for (var i = 1; i < tempS; i++)
    {
        var curChar = str[i];
        for (var j = 0; j < i; j++)
        {
            // check if duplicate
            if (str[j] === curChar)
            {
                console.log("duplicate detected at index ",j,str[j],"and index",i,str[i])
                // we have duplicate! means we could potentially have a repeated set of characters
                // i, j have same character, so let's move both forward
                var aheadLeft=j, aheadRight=i;
                var diff = Math.min(aheadRight-aheadLeft,tempS-aheadRight);
                var repeat = true;
                for (var num = 1; num < diff; num++)
                {
                    // we go backwards...
                    // ashiash ...
                    // we are at __h___h, so now we go
                    // _s__s_
                    console.log("\tis ",str[aheadRight+num],str[aheadLeft+num])
                    if (str[aheadRight+num] !== str[aheadLeft+num])
                    {
                        repeat = false;
                        break;
                    }    
                }
                if (repeat){
                    console.log("found repeat!",str,str[aheadLeft],aheadLeft,str[aheadRight],aheadRight);
                    str = str.substring(0,aheadRight)+str.substring(aheadRight+diff)
                    return removeRepeat(str);
                }
                break;
            }
        }
    }
    return str;
}
console.log("New str: "+removeRepeat("nnnnnnnnzzzzzz1"));

我遇到的问题是算法没有产生正确的结果"Apples and Apples and Oranges"

重复的字符串应该是Apples and，结果应该是 Apples and Oranges 但我得到了

Aples and Apples and Orang

我不确定如何修复我的算法以检查重复项是否是更大图景的一部分。我的一个想法是向后而不是向前穿过绳子。任何想法/提示都会很棒！

*编辑：我在原始示例中不够清楚。

输入Hey Hi Hi Hi Hey Hi Hi Hi应该输出，Hey Hi Hi Hi而不是Hey Hi因为Hi Hi Hi，虽然重复，是较大的一部分Hey Hi Hi Hi

Boots and Cats and Boots and Cats and YO应该等于Boots and Cats Yo不Bots and Cats and Boots and Cats and YO

4

2 回答 2

0

我建议您做的是编写一个删除最长重复项的函数，然后如果您愿意，可以多次调用它。这是我看到的消除规范中（大部分）歧义的最简单方法。

如果您想这样做，请使用您拥有的代码，而不是实际删除代码，只需跟踪将删除的数量以及删除位置。每次您找到删除更多信息的方法时，请更新该信息。

然后，最后，删除找到的最大块（您保留的信息）。

于 2013-06-21T18:15:43.357 回答
0

这将非常接近您的要求。我认为您的两个示例需要稍作更改，但如果没有这些更改，它们似乎没有意义。

在 Javascript 中，

str.replace(/(.+?)(\1)+/g, function(match, group){return group;})

我们在这里所做的是匹配一个字符串（组 1）一次或多次，然后用一个实例替换它。第 1 组匹配是非贪婪的，因此AAAA->A而不是AA.

测试用例：

1) "Apples and Apples and Oranges" -> "Apples and Oranges"
2) "Hey Hi Hi Hi Hey Hi Hi Hi" -> "Hey Hi Hey Hi"
3) "Hey Hi Hi Hi Hey Hi Hi Hi " -> "Hey Hi Hi Hi "
4) "Boots and Cats and Boots and Cats and YO" -> "Boots and Cats and YO"
5) "AAAAZZZZ5" -> "AZ5"

请注意，2) 与问题不匹配，但它需要该空间才能使您正在寻找的重复实际存在。我认为 3) 表明它解决了您所期望的这种情况。

另外，4) 不太匹配，但我认为这是问题中的错字。

于 2013-06-21T21:23:20.000 回答