algorithm - 挤压函数 squeeze(s1,s2)..... 需要建议

Question

我想编写一个压缩函数 squeeze(s1,s2) 来删除 s1 中与字符串 s2 中的任何字符匹配的每个字符。

除了时间复杂度 (m * n) 之外，是否有任何可用的算法，即遍历字符串 s1 m 次(s2 的长度)并跳过所有出现在 s2 中的字符。

谢谢...

Answer 1

创建位图( bool 数组)。

遍历字符串s2，切换对应于一​​个字符的每一位。

遍历字符串s1，如果对应的位为真则跳过该字符。

如果您想允许更多字符，显然要修改长度(下面的示例需要 ToLower()/ToUpper()，因为它使用 26)。

粗略的 C# 概念证明示例(准备粘贴到 LINQPad 中):

void Main()
{
    // Mapping the alpha lower case characters to start at zero
    int magicAsciiAdjust = -96; 

    string s1 = "asdaswerwe"; // Assumes no non-alpha
    string s2 = "asdacbBe"; // Assumes no non-alpha
    string output = String.Empty;

    bool[] mask = new bool[26];
    foreach (char c in s2.ToLower())
    {
        mask[((int)c) + magicAsciiAdjust] = true;
    }
    foreach(char c in s1.ToLower())
    {
        if (!mask[((int)c) + magicAsciiAdjust])
            output += c;
    }
    output.Dump();
}

您可以通过将掩码设为 128 来支持 ASCII。 (并删除 ToLower() 调用)等。