843. Guess the Word

題目網址：https://leetcode.cn/problems/guess-the-word/

題意：給一由不同 string 所組成的單字列表 words, 其中 words[i] 長度均為 6。words 中的一個單字將被選作秘密單字 secret。

另外, 給一輔助對象 Master, 你可以調用 Master.guess(word) 來猜單字, 其中參數 word 長度為 6, 且必須是 words 中的 string。

Master.guess(word) 將會返回以下結果：

若 word 不是 words 中的 string, 則返回 1

返回一個整數, 表示你所猜測的單詞 word 與 secret 的準確匹配（值和位置同時匹配）的數目

此外, 還會給一參數 allowedGuesses, 代表調用 Master.guess(word) 的最大次數。

在不超過允許猜測次數的前提下, 你應該調用 Master.guess 來猜出 secret, 並得到以下結果：

若調用 Master.guess 的次數大於 allowedGuesses or 你沒有用 Master.guess 猜到 secret, 則得到 "Either you took too many guesses, or you did not find the secret word."

若調用 Master.guess 猜到 secret, 且調用 Master.guess 的次數不超過 allowedGuesses, 則得到 "You guessed the secret word correctly."

題目保證你可以透過某種合理的策略（而非暴力法）猜到 secret。

Solution：

想法：利用刪去法

先隨機選擇一單字 s, 然後計算 s 與 secret 的相似度 cnt

若 cnt == 6, 代表 s 為 secret

否則, 遍歷 words 中其他的單字 word, 並計算 s 和 word 的相似度
然後將 count(s, word) == cnt 的單字加到 filter 中
➔ 能這樣做是因為 s 和 secret 的相似度等於 cnt, 若剩下的單字 word 要等於 secret, 則 word 和 s 的相似度必須要等於 cnt

將 words 更新成 filter

重複以上步驟直到 words 為空

e.g. secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"]

假設隨機選到 s = eiowzz, 此時 s 與 secret 的相似度 cnt = 2

遍歷 words 其他單字 word, 並把符合 count(s, word) == 2 的單字加到 filter 中

word = acckzz, count(s, word) = 2 = cnt ➔ filter = {acckzz}

word = ccbazz, count(s, word) = 2 = cnt ➔ filter = {acckzz, ccbazz}

word = abcczz, count(s, word) = 2 = cnt ➔ filter = {acckzz, ccbazz, abcczz}

更新 words ➔ words = {acckzz, ccbazz, abcczz}

假設隨機選到 s = abcczz, 此時 s 與 secret 的相似度 cnt = 4

遍歷 words 其他單字 word, 並把符合 count(s, word) == 4 的單字加到 filter 中

word = acckzz, count(s, word) = 4 = cnt ➔ filter = {acckzz}

word = ccbazz, count(s, word) = 2 != cnt ➔ filter = {acckzz}

更新 words ➔ words = {acckzz}

選 s = acckzz, 此時 s 與 secret 的相似度 cnt = 6, 代表找到 secret

class Solution {
public:
    void findSecretWord(vector<string>& words, Master& master) {
        // 這個數是試出來的, 若用 srand(time(0)) 隨機生成亂數, 有時會成功, 有時會失敗
        srand(1671613492);

        while (!words.empty()) {
            // 先隨機選一單字, 並計算其和 secret 的相似度
            const auto s = words[rand() % words.size()];
            const int cnt = master.guess(s);

            // 若相似度為 6, 代表找到 secret
            if (cnt == 6) {
                return;
            }

            vector<string> filter;

            // 所以遍歷 words 剩下的 word, 計算 word 和 s 的相似度
            // 若 count(s, word) != cnt, 則將 word 剔除掉
            for (const auto& word : words) {
                if (s == word) { // 若為 s, 則跳過
                    continue;
                }

                if (count(s, word) == cnt) {
                    filter.emplace_back(word);
                }
            }

            words = move(filter); // 將 words 更新成 filter
        }
    }

private:
    // 計算 s 和 word 的相似度, 只需 O(1) time, 因為 s、word 的長度必為 6
    int count(const string& s, const string& word){
        int cnt = 0;
        for (int i = 0; i < 6; ++i) {
            if (s[i] == word[i]) {
                ++cnt;
            }
        }
        return cnt;
    }
};

time：$O(n^2)$ ➔ worse case：每次 s 都只從 words 中剔除掉一個 word
故時間複雜度為 $n + (n-1) + (n-2) + … + 1 = O(n^2)$
space：$O(n)$ ➔ filter 的元素個數不超過 n