从字符串中删除指定字符的高效方法

Question

从字符串中删除指定字符的高效方法

calgorithmdata-structures

3

例如，给定一个字符串" Stackoverflow is for every one "和要删除的字符"aeiou"，函数应该将字符串转换为" Stckvrflw s fr vry n "。

我有一个字符串的字符数组：str[]和一个要删除的字符的字符数组：remove[] 我的解决方案是：循环遍历str[]，查找每个需要删除的字符。每次都将str[]向左移动一个位置。我相信还有更好的方法。

- AJ.

请更具体一些。在你的问题中加入你所寻找的时间/空间复杂度。如果我们的解决方案适用于短字符串，我认为O(n^2)是可以接受的。 - dirkgently

非解决方案（A）：告诉面试官切换到Python并使用string.translate(None, "aeiou")。（B）：告诉面试官切换到Perl并使用$string =~ s/[^aeiou]//g。 - kennytm

这是我的推理：一些最好的字符串匹配算法是Theta(n)。您有m个这样的模式要检查（特殊情况：模式长度== 1）。因此，基本上，您正在查看Theta(mn)运行时。 - dirkgently

1

@dirkgently：可以用Theta(m + n)完成，参见下面的我的第三个解决方案。 - Tarydon

@Tarydon：另一件我有意跳过的事情是预处理时间，这个要注意之前我的评论中提到了 :) - dirkgently

6个回答

2

我相信这是其中一个“经典”的难题。

实质上，您需要扫描“match”字符串并创建可能匹配的位表。

然后，您需要遍历一次“src”，并将每个字符与您的表进行比较。

O(n)时间复杂度。

算法大致如下：

   static char bits[32];  // Not thread-safe, but avoids extra stack allocation
   char * dest = src;
   memset(bits, sizeof(bits), 0);  
   for (; *remove; remove++)
   {
      bitfields[*match >> 3] |= *remove & 7;
   }

   for (;*src; src++) 
   {
      if (!((bits[*src >> 3] & (*src & 7)) == (*src & 7)))
      { 
        *dest++ = *src;
      }
   }

我相信ischar()，isdigit()，isspace()等类似于这种技术，但它们的查找表是常量。

- JBRWilkinson

有更简洁的表达方式可以为了学习而做，但我很高兴看到有人理解了它。 - dmckee --- ex-moderator kitten

2

这是我的版本，复制循环中的 if 语句被消除了：

#include <stdio.h>
#include <string.h>

int main( void ){
  unsigned char str[]    = "Stackoverflow is for every one";
  unsigned char remove[] = "aeiou";

  unsigned char table[256] = { [ 0 ... 255 ] = 1 };
  for( unsigned char *r=remove; *r; r++ ){ table[*r]=0; }

  unsigned char *source=str, *dest=str;
  while( (*dest = *source++) ) dest += table[*dest];

  printf( "str: '%s'\n", str );
}

- sambowry

数组初始化使用了GCC扩展，你应该提到它。 - dirkgently

哇 - 编译器特定扩展？那是作弊！ - JBRWilkinson

只有 while 循环是真正的代码，其他行都是伪代码。 - sambowry

-1

我会循环遍历 str[]，并将不在 remove[] 中的每个字符存储到一个新数组中（假设为 new_str[]）。然后交换 new_str[] 和 str[]。

- Gregi

-1

如果您可以再多分配一个缓冲区，您可以：循环遍历str[]中的每个字符并在remove[]中查找，但不是进行移位操作，而是将其复制到新数组中。

- Maris B.

不需要第二个缓冲区......新字符串（以及其每个子字符串）保证不比旧字符串更长，因此您可以使用当前缓冲区的前端作为接收缓冲区。这很危险，容易出错，但时间复杂度为O(n*m)，额外空间复杂度为O(1)。 - dmckee --- ex-moderator kitten

-1

使用正则表达式进行查找和替换是一种更紧凑的解决方案。使用GNU C库或找到另一个支持正则表达式搜索和替换的库。当然，如果每次字符都不同，您将不得不在运行时创建正则表达式。如果您坚持使用当前的方法，请将其拆分为函数。

我也喜欢Tarydon的方法。它更省事！

- batbrat

将正则表达式这样通用而强大的工具用于解决这个问题无疑可以实现，你可能能够用简短优雅的代码完成它，但从快速和需要较少额外空间的角度来看，它并不高效。 - dmckee --- ex-moderator kitten

同意。我的回答是基于 homeWorkBoy 提到了更好的 hack 这一事实。他没有说明是否想要一个更快的算法。现在看来，提供一个更好的算法显然是更好的答案。 - batbrat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tarydon · Accepted Answer

将整个字符串向左移动一个位置将使该算法的时间复杂度变为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  
   }
}

我在这里假设这些是以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;
}