例如,给定一个字符串“Stackoverflow is for every one”并删除“aeiou”, 该函数应将 str 转换为“Stckvrflw s fr vry n”。
我有一个字符串字符数组:str[] 和一个要删除的字符数组:remove[]
我的解决方案:循环 str[] 寻找 remove[] 中的每个字符。每次将 str[] 左移一位。我相信更好的破解是可能的。
最佳答案
将整个字符串左移一个位置将使这成为一个有效的 O(n^2) 算法。您可以在线性时间内就地执行此操作:
void Remove (char * src, const char * match) {
char * dest = src;
for (;;) {
char ch = *src++;
if (!strchr (match, ch)) *dest++ = ch; // Copy chars that don't match
if (!ch) break; // Stop when we copy over a null
}
}
我在这里假设这些都是空终止的。如果不是这种情况,那么您还必须传入长度并适当修改算法。特别是,您将无法使用 strchr。为了完整起见,这里有一个适用于 char 数组(不是以 null 结尾)的版本。
// Removes from str[] (of length strlen), all chars that are found
// in match[] (of length matchlen). Modifies str in place, and returns
// the updated (shortened) length of str.
int Remove (char[] str, int srclen, char[] match, int matchlen) {
int dst = 0, found;
for (int src = 0; src < srclen; src++) {
char ch = str[src];
found = 0; // Search if this char is found in match
for (int i = 0; i < matchlen && !found; i++)
if (match[i] == ch) found = 1;
if (!found) str[dst++] = ch;
}
return dst;
}
最后,我猜这是我们将要得到的最接近 O(n) 的时间。我在这里假设 8 位字符并构建一个查找表,因此它应该在 O(n) + O(m) 中运行,其中 m 是匹配字符串的长度。
int Remove (char* str, int srclen, char* match, int matchlen) {
bool found[256];
for (int i = 0; i < 256; i++) found[i] = 0;
for (int i = 0; i < matchlen; i++) found[match[i]] = 1;
int dst = 0;
for (int src = 0; src < srclen; src++) {
char ch = str[src];
if (!found[ch]) str[dst++] = ch;
}
return dst;
}
关于c - 从字符串中删除指定字符的有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2171387/