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

• 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;
}
};
``````

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