Archie Gertsman - 8 months ago 43

C++ Question

For fun and practice, I have tried to solve the following problem (using C++):

`Given a string, return all the palindromes that can be obtained by rearranging its characters.`

I've come up with an algorithm that doesn't work completely. Sometimes, it finds all the palindromes, but other times it finds some but not all.

It works by swapping each adjacent pair of characters

`N`

`N`

`std::vector<std::string> palindromeGen(std::string charactersSet) {`

std::vector<std::string> pals;

for (const auto &c : charactersSet) {

for (auto i = 0, j = 1; i < charactersSet.length() - 1; ++i, ++j) {

std::swap(charactersSet[i], charactersSet[j]);

if (isPalandrome(charactersSet)) {

if (std::find(pals.begin(), pals.end(), charactersSet) == pals.end()) {

// if palindrome is unique

pals.push_back(charactersSet);

}

}

}

}

return pals;

}

What's the fault in this algorithm? I'm mostly concerned about the functionality of the algorithm, rather than the efficiency. Although I'll appreciate tips about efficiency as well. Thanks.

Answer

This probably fits a bit better in Code Review but here goes:

You change `charactersSet`

while iterating over it, meaning that your iterator breaks. You need to make a copy of `characterSet`

, and iterate over that.

Since `pals`

holds only unique values, it should be a `std::set`

instead of a `std::vector`

. This will simplify some things. Also, your `isPalandrome`

method spells palindrome wrong!

Since palindromes can only take a certain form, consider sorting the input string first, so that you can have a list of characters with an even number of occurrences, and a list of characters with an odd number. You can only have one character with an odd number of occurrences (and this only works for an odd length input). This should let you discard a bunch of possibilities. Then you can work through the different possible combinations of one half of the palindrome (since you can build one half from the other).