36-B中所有字符,看看是不是在A中都出现？（算法）

心已赠人 2022-12-22 08:59 93阅读 0赞

> 写一个函数返回bool值，来判断给定的字符串A和B（假设都是小写字母），  
> 是否是B中的字符都存在于A中，如果是返回true，否则返回false  
> 函数申明如：bool checkString(const char \*A,const char \*B);

#include <stdio.h>
    #include <assert.h>
    #include <string.h>
    #include <stdlib.h>
    //A:"ababcdxyzk",   B:"aababcxxa" ->true
    //A:"ababcdxyzk",   B:"abababcabxyiabc"->false;
    //算法1:遍历B中所有字符,看看是不是在A中出现(遍历A)
    bool checkString1(const char *A,const char *B)//O(n*m)
    {
        
    	assert(A != NULL);
    	assert(B != NULL);
    	const char *q;
    	for(const  char *p=B;*p!='\0';p++)//遍历B
    	{
        
    		for(q=A;*q!='\0';q++)//遍历A
    		{
        
    			if(*p == *q)
    			{
        
    				break;
    			}
    		}
    		if(*q == '\0')
    		{
        
    			return false;
    		}
    	}
    	return true;
    }
    //A:"ababcdxyzk",   B:"aababcxxa" ->true
    //A:"ababcdxyzk",   B:"abababcabxyiabc"->false;
    //算法2:遍历A,将A中的所有字符登记,然后遍历B,看看B中所有字符是否在登记中
    bool checkString(const char *A,const char *B)//O(n+m)
    {
        
    	assert(A != NULL);
    	assert(B != NULL);
    
    	int  chars[26] = {
        0};//登记A中出现的小写字母,出现为1,未出现为0.chars[0]登记'a',chars[1]登记'b'...
    	//'a'->0,'b'->1,'c'->2,'d'->3,...,'z'->25  通项: 字符-'a'   哈希表    y=x-'a';哈希函数
    	while(*A != '\0')//遍历A
    	{
        
    		chars[*A-'a'] = 1;
    		A++;
    	}
    
    	while(*B != '\0')//遍历B
    	{
        
    		if(chars[*B-'a'] == 0)//*B改字符在A中没有出现
    		{
        
    			return false;
    		}
    		B++;
    	}
    
    	return true;
    }
    
    int main()
    {
        
    
        const char *A = "ababcdxyzk";
        const char *B = "aababcxxai";
    	if(checkString(A,B))
    	{
        
    		printf("B中的字符都出现在A中\n");
    	}
    	else
    	{
        
    		printf("B中的字符不是都出现在A中\n");
    	}
    	return 0;
    }