My C++ Brutal Force Beats 99%. What's the Point of the Question?


  • 0
    F

    Not sure why this one is Hard if a straightforward brutal force check can beat 99% of all methods.
    This is a O(nk^2) Brutal force solution. Not using trie or pre-fix/suffix array or anything. And its run time beats 99%.
    So I don't see this question's point.
    And more interestingly, a O(n^2k) brutal force can also be accepted, see my 2nd program, but it has 1580ms run time, which doesn't make sense, because the question doesn't say N is way larger than K, so I can assume K may be way larger than N. In this case, O(nk^2) should run way slower than O(n^2k).
    My point is, O(nk^2) should not be considered a better solution than O(n^2k), but apparently the test cases favor the former.
    Anyway, I don't see the point of this question.

    class Solution {
        bool isPalindrome(const string & word, int start, int end)
        {
            for (int i = 0; i < (end - start)/2; ++i)
                if (word[start + i] != word[end - i - 1])
                    return false;
            return true;
        }
    public:
        vector<vector<int>> palindromePairs(vector<string>& words)
        {
            unordered_map<string, int> dict;
            for (int i = 0; i < words.size(); ++i)
                dict[words[i]] = i;
            vector<vector<int>> results;
            for (int i = 0; i < words.size(); ++i)
            {
                string temp = words[i];
                reverse(temp.begin(), temp.end());
                auto iter = dict.find(temp);
                if (temp != words[i] && iter != dict.end())
                    results.push_back(vector<int>{iter->second, i});
                for (int j = 1; j <= words[i].size(); ++j)
                {
                    if (isPalindrome(words[i], 0, j))
                    {
                        string temp = words[i].substr(j, words[i].size() - j);
                        reverse(temp.begin(), temp.end());
                        auto iter = dict.find(temp);
                        if (iter != dict.end())
                            results.push_back(vector<int>{iter->second, i});
                    }
                    if (isPalindrome(words[i], words[i].size() - j, words[i].size()))
                    {
                        string temp = words[i].substr(0, words[i].size() - j);
                        reverse(temp.begin(), temp.end());
                        auto iter = dict.find(temp);
                        if (iter != dict.end())
                            results.push_back(vector<int>{i, iter->second});
                    }
                }
            }
            return results;
        }
    };
    
    ////O(n^2L) Brutal force
    class Solution {
        bool isPalindrome(const string & word, int start, int end)
        {
            for (int i = 0; i < (end - start)/2; ++i)
                if (word[start + i] != word[end - i - 1])
                    return false;
            return true;
        }
        bool test(vector<string>& words, int idx0, int idx1)
        {
            auto & word0 = words[idx0], word1 = words[idx1];
            int i = 0, j = word1.size() - 1;
            for(;i < word0.size() && j >= 0 ; ++ i, -- j)
                if (word0[i] != word1[j])
                    return false;
            if (j >= 0)
                return isPalindrome(word1, 0, j + 1);
            return isPalindrome(word0, i, word0.size());
        }
    public:
        vector<vector<int>> palindromePairs(vector<string>& words)
        {
            vector<vector<int>> results;
            for (int i = 0; i < words.size(); ++i)
                for (int j = i + 1; j < words.size(); ++j)
                {
                    if (test(words, i, j))
                        results.push_back(vector<int>{i, j});
                    if (test(words, j, i))
                        results.push_back(vector<int>{j, i});
                }
            return results;
        }
    };
    

Log in to reply
 

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