面试100 36在字符串中删除指定的字符

   面试100 在字符串中删除指定的字符

在字符串中删除指定的字符
   输入两个字符串，从第一字符串中删除第二个字符串中所有的字符。
   例如，输入”They are students.”和”aeiou”，
    则删除之后的第一个字符串变成”Thy r stdnts.”。

  (1)思路建立一个256位长度bit数组，存储第二个字符串的每个字符，遍历第一个字符串的时候，根据hash映射，判断该位是否需要删除。
重要的一方面：进行删除操作
    遍历第一个字符串的时候，记录当前已经删除的字符串个数del，然后将不被删除的字符，向前移动del位置。
    这样的话整个字符串的操作的时间复杂度就为o(n)。 del初始为0      
  (2)思路2
     和第一种方法类似，设置了一个指针，deletePtr指向当前删除之后，后序指针预移动的地方，没移动一个字符，deletePtr自增。

二 代码如下：
     

#include <iostream>
 using namespace std ;
 const int N = 50 ;
 
 void del(char * p , char * hash)
 {
      int delcount = 0 ;//记录已经删除的字符数目 
      char * s = p;
      while(*s)      
      {
         if(hash[*s])              
            delcount++ ;                           
          else
            *(s-delcount) = *s ;                                       
         s++ ;            
      }
      *(s-delcount) = '\0' ;
 }
 
 
 int main()
 {
   char s1[N] = "They are students." ; 
   char s2[N] = "aeiou" ;
   char hash[129] ;
   memset(hash , 0 ,sizeof(hash)) ;
   
   char * s = s2;
   while(*s)    //对第二个字符串映射hash函数 
     hash[*s++] = 1 ; 
   
   del(s1 , hash) ;
   cout<<s1<<endl;             
   
   system("pause") ;
   return 0;    
 }

posted on 2011-05-22 22:25 kahn 阅读(1072) 评论(0)  编辑 收藏 引用 所属分类: 算法相关