删除模式串中出现的字符，如“welcome to asted

[问答题]

删除模式串中出现的字符，如“welcome to asted”,模式串为“aeiou”那么得到的字符串为“wlcm t std"，要求性能最优。

查看答案及解析

推荐

有pp才有真相

arron回答三风格（解释/代码/结果），
奉上解释

利用线性hash制作bitmap,使复杂度将为o(M+N),不是传统的o(M*N)
字符串的比较是基础。

考虑大小写情况，

上代码：

//#define _REMOVE // 两处相同的 //删除模式串中出现的字符
#ifdef  _REMOVE
char *removeStr(char *A, char *B)
{
    //大小写相关的话
    int bitMapAll[26][2] = {0}; //ascii 0:0x31 ,A:0x41, B:0x61
    if (A == NULL) return NULL ;
    if (B == NULL) return NULL;
    while (*B != '\0')
    {
        if (  (*B >= 'A' && *B <= 'Z' ) )
            bitMapAll[(*B) - 'A'][1] = 1;
        else if  (*B >= 'a' && *B <= 'z' )
            bitMapAll[(*B) - 'a'][0] = 1;
        B++;
    }
    char *temp = new char[strlen(A)]; //A;//destory it
    int cnt = 0;
    while (*A != '\0')
    {
        if  (*A >= 'A' && *A <= 'Z' )
            if (bitMapAll[(*A) - 'A'][1]) //if(bitMapAll[*A+'A'-'a'])
            {
                A++;
                continue;
            }
        if (*A >= 'a' && *A <= 'z')
            if (bitMapAll[(*A) - 'a'][0])
            {
                A++;;
                continue;
            };
        cnt++;
        *temp = *A;
        A++;
        temp++;
    }
    *temp = '\0';
    return temp - cnt;
}
//40minutes:
//bitmap complex ;反转？
int main()//o(N)
{
    char mA[] = "welcome to asted";
    char mB[] = "aeiou";
    char *A = mA, *B = mB;
    A = removeStr(A, B);
    printf("%s\n", A);
    system("pause");
    delete A;
    return 0;
    //"This is the world"，B="abcdefghi" ,===>A="Ts s t worl"
    //char mA[]="This is the world";
    //char mB[]="abcdefghi";
    //如“welcome to asted”,模式串为“aeiou”
}
#endif

结果图（右侧）：

编辑于 2015-01-29 17:08:09 回复(0)

SwordMaster

void remove_character(string& str, const string& pattern)
{
    unordered_set<char> chars;
    for(unsigned i=0;i<pattern.length();i++)
    {
        chars.insert(pattern[i]);
    }

    unsigned index = 0;
    for(unsigned i=0;i<str.length();i++)
    {
        if(chars.find(str[i]) == chars.end())
        {
            str[index++] = str[i];
        }
    }
    str.resize(index);
}

发表于 2015-01-15 20:27:40 回复(0)

墨儿

inline  bool inString(char c, const  char * _removeString)
{
 char  temp = '\0';
 while ((temp = *_removeString++) != '\0')
 {
 if (temp == c)
 return true;
 }
 return false;
}

//删除模式串中出现的字符，如“welcome to asted”, 
//模式串为“aeiou”那么得到的字符串为“wlcm t std"，要求性能最优。
void removeString(const char * _inputString, const char* _removeString, char * _outputString)
{
 char  temp ='\0';
 while ((temp =*_inputString++) != '\0')
 {
 if (! inString(temp, _removeString))
 {
 *_outputString++ = temp;
 }
 
 }
}

发表于 2015-01-15 11:38:05 回复(0)