哈希之应用--删除字符串

一 问题描述

    两个字符串A、B。从A中剔除存在于B中的字符。比如A=“hello world”,B="er"，那么剔除之后A变为"hllowold"。空间复杂度要求是O(1)，时间复杂度越优越好。

二 解题思路

    利用哈希

如图所示，构造一个哈希表，将字符串B映射到此表中，当要对A进行处理时，只需利用哈希函数进行查找即可。

三 测试效果

四 代码

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

#define Num 52
#define LEN 100
int HashChar[Num];

int Hash(char c) {
    if(!isalpha(c)) return -1;
    if(islower(c)) return c - 'a';
    return c - 'A' + 26;
}
void InitialHash(char *B) {
    int i;
    int pos;
    for(i = 0;B[i];i++) {
        pos = Hash(B[i]);
        if(pos == -1) {
            perror("B contains illegal characters\n");
        }
        else HashChar[pos] = 1;
    }
}
void DelSameStr(char *A, char *B) {
    int i, j;
    int pos;
    i = 0;
    while(A[i]) {
        pos = Hash(A[i]);
        if(HashChar[pos]) {
            for(j = i;A[j];j++) {
                A[j] = A[j + 1];
            }
        }
        else i++;
    }
}
int main() {
    char A[LEN], B[LEN];
    printf("A = ");
    gets(A);
    printf("B = ");
    gets(B);
    InitialHash(B);
    DelSameStr(A, B);
    printf("after coping...");
    puts(A);

    return 0;
}

五 编程体会

    此题要想实现快速查找，哈希是个不错的选择，这个查找的效率为O(1)，而由于哈希表长度固定，所以空间复杂度是O(1)，满足题意。