在另一个字符串中查找部分字符串的正则表达式

Question

我有两个字符串：第一个字符串的值为 "catdog"，第二个字符串的值为 "got"。

我正在尝试查找一个正则表达式，告诉我是否在 "catdog" 中包含了 "got" 的字母。我特别想避免有重复字母的情况。例如，我知道 "got" 是匹配的，但是 "gott" 不匹配，因为 "catdog" 中没有两个 "t"。

编辑：

根据下面 Adam 的回复，这是我在解决方案中使用的 C# 代码。感谢所有回复的人。

注意：我必须将 char 转换为 int 并减去 97 才能获得数组的适当索引。在我的情况下，字母始终是小写。

    private bool CompareParts(string a, string b)
    {

        int[] count1 = new int[26];
        int[] count2 = new int[26];

        foreach (var item in a.ToCharArray())
            count1[(int)item - 97]++;

        foreach (var item in b.ToCharArray())
            count2[(int)item - 97]++;

        for (int i = 0; i < count1.Length; i++)
            if(count2[i] > count1[i])
                return false;

        return true;
    }

- Sailing Judo

---

使用ToList()上的ForEach扩展有更简洁的方法来完成这个任务...我在下面演示了。 - BenAlabaster

Answer 1

你使用的工具不太合适。正则表达式并不容易处理这种情况。幸运的是，没有正则表达式也很容易实现。你只需计算两个字符串中每个字母出现的次数，并比较两个字符串之间的计数 - 如果对于字母表中的每个字母，第一个字符串中的计数至少与第二个字符串中的计数相同，则满足你的条件。由于你没有指定语言，以下是伪代码答案，应该很容易转换成你的语言：

bool containsParts(string1, string2)
{
    count1 = array of 26 0's
    count2 = array of 26 0's

    // Note: be sure to check for an ignore non-alphabetic characters,
    // and do case conversion if you want to do it case-insensitively
    for each character c in string1:
        count1[c]++
    for each character c in string2:
        count2[c]++

    for each character c in 'a'...'z':
        if count1[c] < count2[c]:
            return false

    return true
}

- Adam Rosenfield

---

好的回答 - 但我认为你把返回true和返回false弄反了，不是吗？你不能早早地中断并返回成功，对吗？ - Jonathan Leffler

糟糕，好发现。已经修复了。 - Adam Rosenfield

好的回答 - 以下有一种更简洁的方法来完成这个。 - BenAlabaster

Answer 2

之前已经提出过，也许正则表达式不是最好的方法来实现这个目标，我同意这个观点。然而，你接受的答案有点啰嗦，考虑到你要测试一组字母是否为另一组字母的子集，可以用以下代码只用一行来实现：

MatchString.ToList().ForEach(Item => Input.Remove(Item));

以下是使用方法：

public bool IsSubSetOf(string InputString, string MatchString) 
{
  var InputChars = InputString.ToList(); 
  MatchString.ToList().ForEach(Item => InputChars.Remove(Item)); 
  return InputChars.Count == 0;
}

您可以只调用这个方法来验证它是否是子集。

有趣的是， "got"将返回一个没有任何元素的列表，因为匹配字符串中每个项仅出现一次，但是"gott"将返回一个带有单个项的列表，因为只会有一个调用将"t"从列表中删除。因此，列表中将剩下一个项目。也就是说，"gott"不是"catdog"的子集，但"got"是。

您还可以进一步将该方法放入一个静态类中：

using System;
using System.Linq;
using System.Runtime.CompilerServices;

static class extensions
{
    public static bool IsSubSetOf(this string InputString, string MatchString)
    {
        var InputChars = InputString.ToList();
        MatchString.ToList().ForEach(Item => InputChars.Remove(Item));
        return InputChars.Count == 0;
    }
}

这样做可以将您的方法变成字符串对象的扩展，从长远来看，这将使事情更加容易，因为您现在可以这样调用：

Console.WriteLine("gott".IsSubSetOf("catdog"));

- balabaster

---

你的代码看起来非常优雅，让我忍不住想尝试一下。但某些原因导致你的方法对我不起作用。我将它原封不动地放进了我的项目中，并替换了我调用的方法。此外，它的运行时间几乎比我上面发布的方法长了一倍。 - Sailing Judo

@Sailing Judo：真的吗？我直接从我的项目中复制粘贴过来的。实际上，从这里剪切并粘贴到项目中也完全没问题。虽然LINQ可能不是最快的解决方案，但它的性能足够好，我不会因为速度更快的东西而放弃它... - BenAlabaster

@Sailing Judo：同意，我的表现不是很好，但差距并不大，不能忽略维护的便利性。进行了一次1,000,000,000次迭代的测试比较，你的代码每次迭代平均需要10个时钟周期，而我的则需要16个... - BenAlabaster

是的..确认过了。你的代码对我来说运行良好。我不小心交换了参数。 - Sailing Judo

哦，是的，如果你要循环遍历许多记录，那么性能肯定是一个大问题。不过很高兴你找到了解决方案。 - BenAlabaster

Answer 3

你想要一个字符串，精确匹配那些字母，仅出现一次。这取决于你在哪里编写正则表达式，但它将是类似于：

^[^got]*(g|o|t)[^got]$

如果你有一个“仅匹配一次”的运算符，那会很有帮助。

- Charlie Martin

Answer 4

使用正则表达式的最佳方法是：

A. 对大字符串（搜索空间）中的字符进行排序，将“catdog”转换为“acdgot”

B.

1. 对要搜索字符的字符串执行相同操作：“gott”变成“gott”...

2. 在每个字符之间插入“.*”

3. 将后者用作在前者中搜索的正则表达式。

例如，一些Perl代码（如果您不介意）：

$main = "catdog"; $search = "gott";
# break into individual characters, sort, and reconcatenate
$main = join '', sort split //, $main;
$regexp = join ".*", sort split //, $search;
print "Debug info: search in '$main' for /$regexp/ \n";
if($main =~ /$regexp/) {
    print "Found a match!\n";
} else {
    print "Sorry, no match...\n";
}

这将打印：

Debug info: search in 'acdgot' for /g.*o.*t.*t/
Sorry, no match...

去掉一个“t”，你就能匹配成功。

- bart

Answer 5

我认为使用正则表达式没有合理的方法来完成这个任务。疯狂的方法是写出所有的排列组合：

/^(c?a?t?d?o?g?|c?a?t?d?g?o?| ... )$/

现在，通过一些技巧，您可以使用几个正则表达式来完成这个任务（以下是Perl的示例，未经测试）：

$foo = 'got';
$foo =~ s/c//;
$foo =~ s/a//;
...
$foo =~ s/d//;
# if $foo is now empty, it passes the test.

当然，理智的人会使用循环：

$foo = 'got'
foreach $l (split(//, 'catdog') {
    $foo =~ s/$l//;
}
# if $foo is now empty, it passes the test.

当然，有更好的执行方式来完成这个任务，但它们不使用正则表达式。如果您可以使用Perl的扩展正则表达式功能（如嵌入式代码），那么无疑也有方法可以实现。

- derobert

Answer 6

Charlie Martin几乎做对了，但你必须为每个字母完成一次完整的遍历。你可以通过使用前瞻来完成除最后一次遍历之外的所有遍历，从而使用单个正则表达式实现这一点：

/^
 (?=[^got]*g[^got]*$)
 (?=[^got]*o[^got]*$)
 [^got]*t[^got]*
$/x

这是一个很好的练习，可以磨练你的正则表达式技能，但如果我在实际工作中要做到这一点，我不会用这种方法。非正则表达式方法需要更多的打字，但任何最基本的程序员都能理解和维护它。如果使用正则表达式，那么假设的维护者也必须具备超过最基本的正则表达式能力。

- Alan M

Answer 7

@Adam Rosenfield的Python解决方案：

from collections import defaultdict

def count(iterable):
    c = defaultdict(int)
    for hashable in iterable:
        c[hashable] += 1
    return c

def can_spell(word, astring):
    """Whether `word` can be spelled using `astring`'s characters."""

    count_string = count(astring)
    count_word   = count(word)

    return all(count_string[c] >= count_word[c] for c in word)

- J.F. Sebastian