Re: [閒聊] 每日LeetCode

[fxfxxxfxx (愛麗絲)]

49. Group Anagrams

要把同樣字母組成的字串分在同一組

所以重點在要能知道兩個字串是否由相同字母組成

最簡單的方法是把兩個字串 sort 之後進行比較

所以可以寫一個 hash map 是 string ---> vector<string>

key 就是 sort 過的字串

這樣複雜度會是 O(n klogk), k 是字串長度

雖然 k 上限只有 100 而已，但有個 log 卡在那邊就有點不爽

所以後來改成用 char arr[26] 來存各字母出現的次數
(因為 k <= 100 < 128 所以 char 放的下)

這樣複雜度可以到 O(nk)

    class Solution {
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) {
            unordered_map<string, vector<string>> M;

            for (string & s: strs) {
                char arr[26] = {};
                for (char c: s)
                    arr[c - 'a'] += 1;
                M[string(arr, arr + 26)].push_back(s);
            }

            vector<vector<string>> ans;
            for (auto & [_, v]: M)
                ans.push_back(move(v));

            return ans;
        }
    };


Runtime : 19 ms   (99.99%)
Memory  : 19.5 MB (87.72%)
https://leetcode.com/submissions/detail/831781703/

是說，LeetCode 的執行時間好像不是很穩定

我改個變數名稱，理論上要是一模一樣的程式再丟一次
時間就暴增到 54 ms，所以感覺那個百分比也看看就好

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.130 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1666926548.A.2AE.html
→ Jaka: 大師
→ SiranuiFlare: 看不懂 但是 大師
→ SecondRun: 大師
推 NTHUlagka: 大師
→ Rushia: string(arr, arr + 26) 這裡在幹嘛阿?
→ fxfxxxfxx: 不想自己寫hash, string有內建的hash可以用所以轉成長
→ fxfxxxfxx: 度是16的string
→ fxfxxxfxx: *26
→ Rushia: 那感覺我們概念差不多 只是差在Hash的效率 字串拼接比較
→ Rushia: 費時
推 Pash97143: 我原本用map去辨認輸入的string 沒想到可以用sort