字符串匹配 : Matching words with or without spaces

Question

在以下两个示例中，我想找到一种方法将“b m w”映射到“bmw”，将“ali baba”映射到“alibaba”。

1. “b m w shops”和“bmw”

我需要确定我是否可以将“b m w”写成“bmw”

我想到了这个方法:

从原始字符串中删除空格。这给出了“bmwshops”。现在找到“bmwshop”和“bmw”中的最大公共(public)子串。

第二个例子:

1. “阿里巴巴和四十大盗”和“阿里巴巴和四十大盗”

上述方法在这种情况下不起作用。

是否有任何标准算法可以使用？

Answer 1

听起来您在问这个问题:“如何通过删除(一些)空格来确定字符串 A 是否可以等于字符串 B？”。

你可以做的是遍历两个字符串，只要它们有相同的字符就在两个字符串中前进，否则在第一个有空格时前进，否则返回 false。像这样:

static bool IsEqualToAfterRemovingSpacesFromOne(this string a, string b) {
    return a.IsEqualToAfterRemovingSpacesFromFirst(b)
        || b.IsEqualToAfterRemovingSpacesFromFirst(a);
}
static bool IsEqualToAfterRemovingSpacesFromFirst(this string a, string b) {
    var i = 0;
    var j = 0;
    while (i < a.Length && j < b.Length) {
        if (a[i] == b[j]) {
            i += 1
            j += 1
        } else if (a[i] == ' ') {
            i += 1;
        } else {
            return false;
        }
    }
    return i == a.Length && j == b.Length;
}

以上只是一个稍微修改过的字符串比较。如果您想将其扩展到“最大公共(public)子串”，则采用最大公共(public)子串算法并执行相同的操作:每当您因第一个字符串中的空格而失败时，就跳过它。