string - 字符串匹配：匹配带或不带空格的单词

Question

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

1. “宝马商店”和“宝马”

我需要确定是否可以将“bm w”写为“bmw”

我想到了这种方法：

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

第二个例子：

1. 《阿里巴巴与四十大盗》和《阿里巴巴与四十大盗》

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

有没有可以使用的标准算法？

Answer 1

您是否看过后缀数组- http://en.wikipedia.org/wiki/Suffix_array 或 Jon Bentley 的这里 -编程珍珠

注意：您必须编写代码来处理空格。

Answer 2

听起来您在问这个问题：“如何通过删除（一些）空格来确定字符串 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;
}

以上只是一个稍微修改过的字符串比较。如果您想将此扩展到“最大公共子字符串”，则采用最大公共子字符串算法并做同样的事情：每当您由于第一个字符串中的空格而失败时，只需跳过它即可。