題目

1684. Count the Number of Consistent Strings
難度: 超級簡單

題意

給定一字串allowed代表合法的字元，求字串陣列words中，只有合法字元出現的字串，有幾個。

方向

先用一個table紀錄allowed出現的字元，因為題目限定小寫的英文字母，所以開一個大小為26的bitset來存；如果字元範圍很大可以改用hash map做。
接著設定總數為零，一一檢查words字串之中的每個字元，若全部符合則總數加一，若有不符合的可以early return

實作

class Solution
{
public:
    int countConsistentStrings(string allowed, vector<string> &words)
    {
        bitset<26> allow(false);

        int res = 0;
        for (auto c : allowed)
            allow[c - 'a'] = true;

        for (auto word : words)
        {
            bool is_allowed = true;
            for (auto c : word)
            {
                is_allowed &= allow[c - 'a'];
                if(!is_allowed)
                    break;
            }
            if (is_allowed)
                res++;
        }
        return res;
    }
};

分析

words數量總長N
時間複雜度: O(N)，每個字元最多檢查一次。
空間複雜度: O(1)，table大小固定為26。

結果

雜談

9月鐵人賽開寫以來，題目都好簡單，要是面試也這麼輕鬆就好了(?

今天1點回家等冷氣師傅來裝新冷氣，結果5點才來，7點裝好...
終於有新冷氣吹了OAO
還好今天是easy題，吹著新冷氣寫個水題+1好愜意XD