c++ - 从字符串中删除指定字符 - 高效的方法(时间和空间复杂度)

Question

问题是:从给定的字符串中删除指定的字符。

Input: The string is "Hello World!" and characters to be deleted are "lor"
Output: "He Wd!"

解决这个问题涉及两个子部分:

1. 判断是否要删除给定的字符
2. 如果是，则删除该字符

为了解决第一部分，我将要删除的字符读取到 std::unordered_map 中，即我解析字符串“lor”并将每个字符插入 HashMap 中。稍后，当我解析主字符串时，我将以每个字符为键查看此 hashmap，如果返回值不为零，则从字符串中删除该字符。

问题 1:这是最好的方法吗？

问题 2:对于这个问题，哪个更好？ std::map 还是 std::unordered_map？因为我对排序不感兴趣，所以我使用了 unordered_map。但是创建哈希表的开销会更高吗？在这种情况下该怎么办？使用map(平衡树)还是unordered_map(哈希表)？

现在进入下一部分，即从字符串中删除字符。一种方法是删除字符并从该点开始向后移动一个位置的数据。在最坏的情况下，我们必须删除所有字符，这将花费 O(n^2)。

第二种方法是只将需要的字符复制到另一个缓冲区。这将涉及分配足够的内存来保存原始字符串并逐个字符地复制，而忽略要删除的字符串。虽然这需要额外的内存，但这将是一个 O(n) 操作。

第三种方法是从第 0 个位置开始读写，每次读取时递增源指针，仅在写入时递增目标指针。由于源指针将始终与目标指针相同或领先于目标指针，因此我可以覆盖相同的缓冲区。这样可以节省内存，也是一个 O(n) 的操作。我正在做同样的事情并在最后调用 resize 来删除额外的不必要的字符？

这是我写的函数:

// str contains the string (Hello World!)
// chars contains the characters to be deleted (lor)
void remove_chars(string& str, const string& chars)
{
    unordered_map<char, int> chars_map;

    for(string::size_type i = 0; i < chars.size(); ++i)
        chars_map[chars[i]] = 1;

    string::size_type i = 0; // source
    string::size_type j = 0; // destination
    while(i < str.size())
    {
        if(chars_map[str[i]] != 0)
            ++i;
        else
        {
            str[j] = str[i];
            ++i;
            ++j;
        }
    }

    str.resize(j);
}

问题 3:我可以通过哪些不同的方式改进此功能。或者这是我们能做的最好的事情吗？

谢谢!

Answer 1

干得好，现在了解标准库算法并提升:

str.erase(std::remove_if(str.begin(), str.end(), boost::is_any_of("lor")), str.end());