LeetCode 49. Group Anagrams

🧩 PROBLEM - LeetCode 49. Group Anagrams

LINK: https://leetcode.com/problems/group-anagrams/description/

Given an array of strings strs, group the anagrams together. You can return the answer in any order..

Return the head of the merged linked list.

Example.

[1]

Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]

Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]

Constraints:

1 <= strs.length <= $10^4$

0 <= strs[i].length <= 100

strs[i] consists of lowercase English letters.

---

Problem anaylsis

1. Make Hash Table.
2. Hash condition should be key that has same alphabet.
3. sorting vs bitmask
4. bitmaks is impossible, 26 of alphabet are ok, but the specific alphabet can have over 1.
5. if i choice sorting, i should reduce the complex.

–MAKING MYSELF 14 ~ 18ms

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
            std::sort(strs.begin(), strs.end(), [](std::string& str1, std::string& str2)
        {
            return str1.length() < str2.length();
        });

    std::vector<std::vector<std::pair<int, int>>> vctIdx;
    int i32Size = strs[0].length();
    vctIdx.emplace_back();
    vctIdx[0].push_back(std::pair<int, int>(0, 0));

    for (int i = 1; i < (int)strs.size(); ++i)
    {
        if (i32Size != strs[i].length())
        {
            i32Size = strs[i].length();
            vctIdx.emplace_back();
        }

        vctIdx.back().push_back(std::pair<int, int>(i, 0));
    }

    for (int i = 0; i < (int)vctIdx.size(); ++i)
    {
        std::vector<std::pair<int, int>>& vctCur = vctIdx[i];
        int i32Size = strs[vctCur[0].first].length();

        for (int j = 0; j < (int)vctCur.size(); ++j)
        {
            std::string& strCur = strs[vctCur[j].first];
            const char* I8Str = strCur.data();
            int i32Value = 0;

            for (int i32Idx = 0; i32Idx < i32Size; ++i32Idx)
            {
                i32Value += (int)*I8Str;
                I8Str++;
            }

            vctCur[j].second = i32Value;
        }

        std::sort(vctCur.begin(), vctCur.end(), [](std::pair<int, int> pair1, std::pair<int, int> pair2)
            {
                return pair1.second < pair2.second;
            });
    }

    std::vector<std::vector<std::string>> vctResult;

    for (int i = 0; i < (int)vctIdx.size(); ++i)
    {
        std::vector<std::pair<int, int>>& vctCur = vctIdx[i];
        std::vector<std::pair<int, int>> vctSameSize;

        bool bContinue = false;
        int i32CheckSize = int(vctCur.size()) - 1;

        for (int j = 0; j < i32CheckSize; ++j)
        {
            if (vctCur[j].second == vctCur[j + 1].second)
            {
                if (!bContinue)
                {
                    vctSameSize.emplace_back();
                    vctSameSize.back().first = j;
                    bContinue = true;
                }
            }
            else
            {
                if (bContinue)
                    vctSameSize.back().second = j;
                else
                {
                    vctSameSize.emplace_back();
                    vctSameSize.back().first = j;
                    vctSameSize.back().second = j;
                }

                bContinue = false;
            }
        }

        if (bContinue)
            vctSameSize.back().second = i32CheckSize;
        else
            vctSameSize.emplace_back(i32CheckSize, i32CheckSize);


        for (int j = 0; j < (int)vctSameSize.size(); ++j)
        {
            int i32First = vctSameSize[j].first;
            int i32Second = vctSameSize[j].second;

            if (i32First == i32Second)
            {
                vctResult.emplace_back();
                vctResult.back().emplace_back(strs[vctCur[i32First].first]);
            }
            else
            {
                std::vector<std::pair<int, std::string>> vctCheckSet;

                for (int k = i32First; k <= i32Second; ++k)
                {
                    vctCheckSet.emplace_back(k, strs[vctCur[k].first]);

                    std::sort(vctCheckSet.back().second.begin(), vctCheckSet.back().second.end(), [](char& c1, char& c2)
                        {
                            return c1 < c2;
                        });
                }

                std::vector<bool> vctCheckin(vctCheckSet.size(), false);
                std::vector<std::vector<int>> vctGroup;

                if (vctCheckSet.size() < 2)
                    int i32Error = 0;

                for (int k = 0; k < (int)vctCheckSet.size(); ++k)
                {
                    std::string strBasic = vctCheckSet[k].second;

                    if (!vctCheckin[k])
                    {
                        vctCheckin[k] = true;
                        vctGroup.emplace_back();
                        vctGroup.back().push_back(vctCheckSet[k].first);

                        for (int m = k + 1; m < (int)vctCheckSet.size(); ++m)
                        {
                            if (!vctCheckin[m] && vctCheckSet[m].second == strBasic)
                            {
                                vctGroup.back().push_back(vctCheckSet[m].first);
                                vctCheckin[m] = true;
                            }
                        }
                    }
                }

                for (int k = 0; k < (int)vctGroup.size(); ++k)
                {
                    vctResult.emplace_back();

                    for (int m = 0; m < (int)vctGroup[k].size(); ++m)
                    {
                        int i32Index = vctGroup[k][m];
                        vctResult.back().push_back(strs[vctCur[i32Index].first]);

                    }
                }
            }
        }
    }

    return vctResult;
    }
};

The process

1. I think i should have to use sorting.
2. Just sorting and compare all of thing are not good.
3. First distinguishing is based on counting of string.
4. Second distinguishing is based on sum of ASCII value if the counting is same.
5. Final distinguishing is based on sorting if First, Second is same.

—- RENEWAL —- I think hash is impossible with simple, but same category is key and real value is original string. That’ll be working well.

– 177ms (Search is linear complex)

    std::vector<std::pair<std::string, std::vector<int>>> vctHash;

    for (int i = 0; i < (int)strs.size(); ++i)
    {
        std::string strV = strs[i];
        std::sort(strV.begin(), strV.end(), [](char& c1, char& c2)
            {
                return c1 < c2;
            });

        bool bIncluded = false;

        for (int j = 0; j < (int)vctHash.size(); ++j)
        {
            if (vctHash[j].first == strV)
            {
                vctHash[j].second.push_back(i);
                bIncluded = true;
                break;
            }
        }

        if (!bIncluded)
        {
            vctHash.emplace_back();
            vctHash.back().first = strV;
            vctHash.back().second.push_back(i);

        }
    }

    std::vector<std::vector<std::string>> vctResult;

    for (int i = 0; i < (int)vctHash.size(); ++i)
    {
        vctResult.emplace_back();

        for (int j = 0; j < (int)vctHash[i].second.size(); ++j)
            vctResult.back().push_back(strs[vctHash[i].second[j]]);
    }

– USE std::unordered_map 4 ~ 18ms

std::unordered_map<std::string, std::vector<std::string>> mapHash;

for (int i = 0; i < (int)strs.size(); ++i)
{
    std::string strV = strs[i];
    std::sort(strV.begin(), strV.end(), [](char& c1, char& c2)
        {
            return c1 < c2;
        });

    mapHash[strV].emplace_back(std::move(strs[i]));
}

std::vector<std::vector<std::string>> vctResult;

for (auto& iters : mapHash)
{
    vctResult.emplace_back();
    std::swap(iters.second, vctResult.back());
}

---

---

Anaylsis

• CHECK SCOPE -> INPUT SIZE
  • Under Hundred: O($2^n$)
  • Under thousand : O($n^2$)
  • Under 10K: O(N $\log{N}$)
  • Under 1M ~ over: O( $\log{n}$)
• COMPLEXITY
  • Time complexity
  • Space complexity
• Check Valid DataType
  • Overflow
• SIMULATION
  • Check test case by myself
• Compare with other people solutions

---

---