拼写单词--仿造哈希表的思想

0x01.问题

给你一份『词汇表』（字符串数组） words 和一张『字母表』（字符串） chars。

假如你可以用 chars 中的『字母』（字符）拼写出 words 中的某个『单词』（字符串），那么我们就认为你掌握了这个单词。

注意：每次拼写时，chars 中的每个字母都只能用一次。

返回词汇表 words 中你掌握的所有单词的 长度之和。

输入示例：words = ["cat","bt","hat","tree"], chars = "atach"

输出示例：6

 解释：可以形成字符串 "cat" 和 "hat"，所以答案是 3 + 3 = 6。

提示：

1 <= words.length <= 1000

1 <= words[i].length, chars.length <= 100

所有字符串中都仅包含小写英文字

C++函数形式为    int countCharacters(vector<string>& words, string chars) 

 0x02.分析问题

题目的需求其实很简单，只需要字母表中的相应字符词汇表每个单词的相应字符要多，就能认定掌握单词。

既然这样，字母表的作用其实就是提供相应字符的数量，仅此而已，然后对于字符串，遍历每个字符是必须的，遍历每个字符的时候，都考虑一下字母表中的字符是否还足够，不足够就直接退出循环，足够就一直遍历下去，如果能遍历完，说明这个单词可以掌握。

我们的问题就简化到了如何记录相应字符的个数，毫无疑问，第一思路肯定是哈希表，的确，用哈希表也可以很快的解决，但是，有了昨天的前车之鉴，我开始思考更加高效的方法。

用哈希表肯定时间还是会稍长一点，我们可以用一个数组仿造出哈希表，因为这些字母都是有规律的，无非就是0-26个连续字符，而且在ASCII表中还是连续存在的，所以我们就可以直接拿下标当键值用，这样访问的效率非常高。

这就是用数组仿造的哈希表。

0x03.解决代码

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        int count=0,i,j;
        vector<int> Table(26,0);
        for(int i=0;i<chars.size();i++){
            Table[chars[i]-'a']++;
        }
        for(i=0;i<words.size();i++){
            vector<int> Table1(Table);
            for(j=0;j<words[i].size();j++){
                if(Table1[words[i][j]-'a']==0) break;
                else Table1[words[i][j]-'a']--;
            }
            if(j==words[i].size()) count+=words[i].size();
        }
        return count;
    }
};

注意每次开始遍历一个字符串的时候，要初始化表中的内容。

0x04.复杂度分析

• 时间复杂度主要由遍历字符串产生，遍历字符串的每个字符可以忽略不计，整体来说是 O（N）。
• 空间复杂度主要由两个数组产生，最大空间为52，可以忽略不计，认为是 O（1）。
• 这应该算是最高效的方法了，不能再继续优化。

ATFWUS  --Writing  By 2020--03--17