CODEWITHSUNDEEP
c++algorithmpalindrome
Roshnal
Roshnal

Reputation: 1314

Comparing strings excluding punctuation and whitespace

I'm making a program to find the larges palindrome in C++ and I need to get the palindromes for the inputted strings ignoring the case, punctuation and whitespace. For example, see the following line:

Confusius say: Madam, I'm Adam.

Here, the largest palindrome is Madam, I'm Adam if you ignore case, punctuation and whitespace.

The program also have to be efficient so as to test strings with 2000 characters in < 1 second. So I have the following code for returning the largest palindrome:

string largestPal(string input_str) {
    string isPal = "";
    string largest = "";

    int j, k;
    for(int i = 0; i < (input_str.length() - 1); ++i) {
        k = i + 1;
        j = i - 1;

        if(j >= 0 && k < (input_str.length())) {
            if(input_str[i] == input_str[j])
                j--;
            else if(input_str[i] == input_str[j])
                k++;
        }

        while(j >= 0 && k < (input_str.length())) {
            if(input_str[j] != input_str[k])
                break;

            else {
                j--;
                k++;
            }

            isPal = input_str.substr(j + 1, k - j - 1);
            if(isPal.length() > largest.length()) {
                largest = isPal;
            }
        }
    }
    return largest;
}

And I tried entering a fully-formatted string (without whitespace, punctuateion and case) as the parameter to this method and have succeeded in getting the output I want. (for example, the previous example returns MADAMIMADAM as the largest palindrome.

The question:

How can I convert this string back to the way it was (with punctuation, whitespace and case)?

OR

How can I test the stripped string directly within the method largestPal, but return the original string (unstrippped) that corresponds to the selected largest palindrome?

Any help greatly appreciated!

Upvotes: 0

Views: 2509

Answers (3)

Karoly Horvath
Karoly Horvath

Reputation: 96286

You have to store the character positions when searching for a palindrome. So the return valu should be a position pair, not a string.

Then just process the original string a similar way you did when you stripped the string. Skip whitespaces and punctiation, and count the letters to find the starting and ending position.

Upvotes: 0

Matthieu M.
Matthieu M.

Reputation: 300139

There are two strategies:

  • play with the unmodified string, with a system of slices and a specific comparator
  • use a canonical version to look for palindromes, but remember where they came from

Given that you elected the second strategy, all that is left is remember where in the original string you were. If you memorize the index of the first letter of the palindrome, then you can just count letters to retrieve the palindrome in the original string.

Upvotes: 2

David Schwartz
David Schwartz

Reputation: 182827

The easiest way is to make a table that maps the characters in the stripped string to their original positions in the unstripped string.

So for example, if the input is "a V, v", your stripped string would be "avv". And your map would be 1,3,6. This indicates that the first character in the stripped string is the first of the unstripped, the next is the third, the next is the sixth. Make this map as you strip the string.

When you you have your final output, find it in the stripped string. Look up the indexes in the original string for the first and last characters in the stripped string, and then output that range of characters.

So for "avv" 1,3,6, your stripped output would be "vv". You find the "vv" in "avv" and look up the corresponding indexes and get 3,6 -- so you want to output characters 3-6 inclusive in the original string, or "V, v".

Upvotes: 2

Related Questions