LeetCode 1160：拼写单词

ps：是非常非常简单的一道题，但是实现途中意识到自己代码能力太差，c++ string的用法搞的一塌糊涂，还是要拉出来总结一下

题目描述

标准解法 哈希表计数 $O(n+m)$

unorder_map分别记录chars（资源）和words中的单词（需求）的字母出现次数，若资源大于需求则满足，否则不满足。

// include <unordered_map>

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        int ans = 0;
        unordered_map<char, int> chars_cnt;
        
        for (auto c : chars) {
            chars_cnt[c]++;
        }

        for (auto word : words) {
            unordered_map<char, int> word_cnt;
            bool flag = true;

            for (auto c : word) {
                word_cnt[c]++;
            }
            for (auto c : word) {
                if (chars_cnt[c] < word_cnt[c]) {
                    flag = false;
                    break;
                }
            } 
            if (flag) {
                ans += word.size();
            }
        }
        return ans;
    }
};

个人解法 $O(n*m)$

没脑暴力的做法，对于words里的每个词的每个字母，在chars中找，找到一个删一个，如果有一个没找到，则不满足要求。

class Solution {
public:
    int countCharacters(vector<string>& words, string chars) {
        int ans = 0;

        for (auto it = words.begin(); it != words.end(); it++) {
            string tmpchars = chars;
            bool flag = true;
            for (auto c = it->begin(); c != it->end(); c++) {
                auto pos = tmpchars.find(*c);

                if (pos != string::npos) {
                    tmpchars.erase(pos, 1);
                }
                else {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                ans += it->size();
            }
        }
        return ans;
    }
};

总结

有一个神秘的现象时，本人的$O(n*m)$方案比题解$O(n+m)$方案的实际耗时要少，也许unordered_map的初始化、增添等代价要比string的使用代价高，或者string内部优化了find()。

从思路来讲，题解采用哈希表计数，通过比对资源与需求来判断单词是否可以被成果拼写，这个思路很巧妙。

在本题中使用到的C++特性总结

• unordered_map<key, value>
  • 正常哈希表的使用方法，重载了[]，可以很方便地类似数组使用
• for(it : container)
  • for_each的用法太赞了，以前不知道，每次遍历都要苦苦写长长的iterator
• string
  • size_t str.find(substr/char)：find可以用来查找子串，也可以查找单个char，返回的是该子串/字母第一次出现的位置，如果找不到,返回str.npos。注意不要用int型变量接收返回值（如int pos = str.find(xxx)，会将str.npos转为-1，从而(pos != str.npos)的判断语句就会失效。标准的接收变量是size_t或简便的auto
  • str.erase(pos, n)，从pos开始删除n个字符，如果省略n的话默认是到结尾。千万注意这里的pos是size_t型（也可以传入int），之前错以为可以删除特定字母c，从而造成错误的用法是str.erase(c)，这里语义是将从c的ASCII码位置起，到字符串结尾的字符删除，而这个ASCII码通常很大，就会造成程序出错。
    • str.erase(iterator pos)和str.erase(iterator first, iterator last)，erase的重载方法，注意区分使用。