Leetcode1160. 拼写单词（C语言）

àì夳堔傛蜴生んèń 2023-07-16 04:00 9阅读 0赞

# Leetcode1160. 拼写单词（C语言） #

**题目：**  
给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。  
假如可用 chars 中的字符拼写出 words 中的某个字符串，每个字符只能用一次，就为掌握了这个单词。返回词汇表 words 中你掌握的所有单词的 长度之和。例 ：  
*输入：words = \[“cat”,“bt”,“hat”,“tree”\], chars = “atach”  
输出：6*  
解释：  
可以形成字符串 “cat” 和 “hat”，所以答案是 3 + 3 = 6。

**思路：**  
将chars，words\[i\] 的字符和个数均存储在哈希表中，进行比较。

**代码：**

int countCharacters(char ** words, int wordsSize, char * chars){
        
        int len=strlen(chars);
        if(wordsSize==0 || len==0)  return 0;
    
        int hash[26];					//构造chars的哈希表
        memset(hash,0,sizeof(hash));	//字符&数量 哈希类型
        for(int i=0;i<len;i++){
        
            hash[chars[i]-'a']++;
        }
    
        int cnt[26];
        int j;
        int max=0;
        for(int i=0;i<wordsSize;i++){
        
            int wlen=strlen(words[i]);
            if(wlen>len)    continue;	//chars长度比words[i]长度小则pass
            
            memset(cnt,0,sizeof(cnt));
            for(j=0;j<wlen;j++){
        
                if(hash[words[i][j]-'a'] <= cnt[words[i][j]-'a'])  //"="hash值为0(j=0时)
                	break;				// "<"重复字母不足
                cnt[words[i][j]-'a']++; //字母重复一次
            }
            if(j==wlen) max+=wlen;
        }
        return max;
    }