20 line C++ 169 ms Beats 100% & Why I think this problem is not properly judged.


  • 2
    F

    The following simple naive brutal force easily beats 100% C++ submission from the past 6 months!

    You know why your algorithm was slower?
    Because you are too smart!

    DO NOT memorize the intermediate results and DO NOT use trie. The additional data structure slows the algorithm down!!

    This is why I think this problem is not properly judged. The judge system should favor smarter solutions, like DP (DFS with memorization) or Trie over a naive solution like mine.

    And truth to be told, this brutal force naive one is actually my 3rd attempts: Trie is MLE, DFS with memorization is too slow (220 ms)...

    class Solution {
        vector<string> results;
        unordered_set<string> dict;
        int min_len = 1;
        bool isConcatenated(string const & word)
        {
            if (dict.count(word)) return true;
            for (int i =  min_len; i < word.size() - min_len + 1 ; ++ i)
                if (dict.count(word.substr(0, i)) > 0 && isConcatenated(word.substr(i, word.size() - i)))
                    return true;
            return false;
        }
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            sort(words.begin(), words.end(), [](const string &lhs, const string &rhs){return lhs.size() < rhs.size();});
            min_len = max(1ul, words.front().size());
            for (int i = 0; i < words.size(); dict.insert(words[i++]))
                if (words[i].size() >= min_len * 2 && isConcatenated(words[i]))
                    results.push_back(words[i]);
            return results;
        }
    };
    

    This is my Trie which got a MLE

    ///Passed all cases but last one got a MLE (memory limit exceeded).
    struct TrieNode
    {
        const static char BEGC = '`', ENDC = '{';
        TrieNode * m_children[27] = {nullptr};
        TrieNode(char c = BEGC)
        {
        }
        inline const TrieNode * operator[](char c) const
        {
            return m_children[c - 'a'];
        }
        inline TrieNode *& operator[](char c)
        {
            return m_children[c - 'a'];
        }
        virtual ~TrieNode ()
        {
            for (auto ptr : m_children)
                delete ptr;
        }
    };
    struct Trie
    {
        TrieNode* root;
        const static char BEGC = TrieNode::BEGC, ENDC = TrieNode::ENDC;
        virtual ~Trie()
        {
            delete root;
        }
        Trie()
        {
            root = new TrieNode();
        }
        void insert(const string & word)
        {
            TrieNode *cur_node_ptr = root;
            for (const auto c : word)
            {
                TrieNode &cur_node = *cur_node_ptr;
                if (cur_node[c] == nullptr)
                    cur_node[c] = new TrieNode(c);
                cur_node_ptr = cur_node[c];
            }
            TrieNode &cur_node = *cur_node_ptr;
            if (cur_node[ENDC] == nullptr)
                cur_node[ENDC] = new TrieNode(ENDC);
        }
    };
    class Solution {
        vector<string> results;
        Trie trie;
        bool isConcatenated(string const & word, int start)
        {
            TrieNode * cur_node_ptr = trie.root;
            for (int i = start; i < word.size(); ++i)
            {
                TrieNode & cur_node = *cur_node_ptr;
                if (cur_node[Trie::ENDC] != nullptr && isConcatenated(word, i))
                    return true;
                cur_node_ptr = cur_node[word[i]];
                if (cur_node_ptr == nullptr)
                    return false;
            }
            if ((*cur_node_ptr)[Trie::ENDC] != nullptr)
                return true;
            return false;
        }
    public:
        vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
            sort(words.begin(), words.end(), [](const string &lhs, const string &rhs){return lhs.size() < rhs.size();});
            for (auto word : words)
            {
                if (word.empty())
                    continue;
                if (isConcatenated(word, 0))
                    results.push_back(word);
                trie.insert(word);
            }
            return results;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.