0

我正在尝试扩展此正则表达式以列出给定字母集的所有可能的字谜：

^(?!.*([aer]).*\1)(?!(.*d){4})([aerd]*|[a-z])$

到目前为止，基于这个正则表达式，我可以接收到由字母“dadder”组成的单词和子单词的任何组合的匹配，例如“adder”、“add”、“ad”、“red”等。正则表达式复杂而不是简单[dadder]*的原因是因为显然每个字母可以匹配无限次，这很糟糕，我希望每个字母只匹配测试字符串一次，如果提供两个 d，它最多可以匹配只有两次或更少。如果有人当然可以简化正则表达式以匹配指定 X 次精确的任何字母组合，请随时提供它:)

然而我的主要问题是，我现在想加入一个句号字符“。”。如果在字符列表中遇到句号，它将充当通配符并且可以匹配任何字符 az。所以dadd.r可以匹配daddzr, daddor,daddpr等rpdadd。

有人可以帮我吗？

4

3 回答 3

1

这不是一个应该用正则表达式解决的问题，因为nhahtdh 的有趣答案应该会让你信服。

正则表达式擅长匹配模式。它们不是解决基于集合的问题的工具，而这正是您尝试使用它们的目的。

你真的需要一种算法方法，因为这是问题的本质。 这个问题只涵盖了这样一个主题。

于 2013-03-01T11:39:57.620 回答
1

问题的第一部分是这个问题的重复：检查字符串是否是一堆字符的子集？（正则表达式）？

该答案专门用于解决您面临的实际问题（问题的第二部分）。

一个非常简单的解决方案是使用 2 个映射：一个映射原始集中字符的频率，并记下 的数量.，另一个映射每个输入字符串的字符频率。

伪代码：

// I assume the maps return 0 for non existent entries
// Depending on the input, the map can simply be an array, or a tree/hash map

function checkAnagramExtended(originalString, inputString):
    if (inputString.length > originalString.length):
        return false

    // The frequency mapping for original string (ref stands for reference)
    // Ideally, refMap should be filled up once instead of every call
    // to this function
    var refMap = countFrequency(originalString)
    // The frequency mapping for input string
    var inpMap = empty map

    foreach (character c in inputString):

        if (inpMap[c] >= refMap[c]):
            // You may want to check that c is a character allowed
            // to be substituted by dot .
            // if (!canBeSubstitutedByDot(c)):
            //     return false

            if (inpMap['.'] >= refMap['.']):
                return false
            else:
                inpMap['.'] += 1

        else:
            inpMap[c] += 1

    return true

附录：扩展正则表达式解决方案？

您的点.扩展名允许a-z匹配任何字符，这使得正则表达式解决方案变得更加不切实际。

在我对另一个问题的解决方案中，我严重依赖负前瞻来断言特定字符的计数小于多字符集中的最大字符数。

点.扩展名可以改变任何字符允许的最大字符数，因此打破了我上面的解决方案。如果你强制正则表达式来完成这项工作，那么如果只有 1 就可以生成正则表达式.，但是当你将它增加到 2 时事情会爆炸。

于 2013-03-01T12:15:23.087 回答
0

好的，在尝试将其作为正则表达式进行大量工作之后，由于不完整的通配符支持和缓慢的处理时间，我放弃了。

我现在已经将我的需求转换为 C# 函数，实际上我现在更舒服、更快乐了，因为它也快了大约 400%，这很棒。

这将检查给定的单词是通过 (.) 支持通配符的一组字母的字谜或子字谜。

letters要测试字谜的字母在哪里。

dictionaryData要测试的单词在哪里List<string>。

var letterCounts = letters.Select(x => x)
  .GroupBy(x => x)
  .ToDictionary(x => x.Key, x => x.Count());

var containsWildcards = letters.IndexOf('.') >= 0;
foreach (var dictWord in dictionaryData)
{
    var matches = 0;
    var dictWordLength = dictWord.Length;
    if (dictWordLength > letters.Length)
        continue;
    var addedChars = new List<char>();
    foreach (var dictLetter in dictWord)
    {
        var foundLetter = false;
        if (letterCounts.ContainsKey(dictLetter) &&
            addedChars.Count(x => x == dictLetter) < letterCounts[dictLetter])
        {
            if (letters.IndexOf(dictLetter) >= 0)
                foundLetter = true;
        }
        else if (containsWildcards &&
            addedChars.Count(x => x == '.') < letterCounts['.'])
        {
            addedChars.Add('.');
            foundLetter = true;
        }
        if (foundLetter)
        {
            addedChars.Add(dictLetter);
            matches++;
        }
        if (dictWordLength == matches)
            break;
    }

    if (dictWordLength <= matches)
    {
        // We have a match!
    }
}

希望它也可以帮助别人。

于 2013-03-01T14:25:26.147 回答