7
\$\begingroup\$

Can I please have some advice on optimizing, cleaning up my code, and places where I could save space/time?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool pal_perm(char*);
int main()
{
    printf("The output is %sa palindrome.\n", pal_perm("abbas")? "": "not "); //Output: The output is a palindrome.
    printf("The output is %sa palindrome.\n", pal_perm("deeds")? "": "not "); //Output: The output is a palindrome.
    printf("The output is %sa palindrome.\n", pal_perm("dead")? "": "not "); //Output: The output is not a palindrome.
    return 0;
}

bool pal_perm(char* str)
{
    char alpha[256];
    int oddCount =0;
    int size = strlen(str);
    memset(alpha, 0, sizeof(alpha)); 

    //see how many occurances of each letter
    for(char ch = 'a'; ch <= 'z'; ch++)
    {
        for(int i=0; i < size; i++)
        {
            if(str[i] == ch)
                alpha[str[i]]++;
        }
    }

    //count the number of times a letter only appears once
    for(int j=0; j<256; j++)
    {
        if(alpha[j] == 1 || (alpha[j]%2==1))
            oddCount++;

    }
    //if there is more than one letter that only occurs, then it 
    //cannot be a palindrome.
    if(oddCount <= 1)
        return true;
    else
        return false;
}
| improve this question | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Your comments re: "only appears once" are not in sync with your code (appears an odd number of times) \$\endgroup\$ – jcaron Dec 29 '15 at 17:45
  • \$\begingroup\$ Yes, you are right. That was a later edit i added and forgot to change the comments. Thank you for showing me! \$\endgroup\$ – Jonathan Dec 29 '15 at 19:06
11
\$\begingroup\$

Strange output

What is a user to think when seeing such output of a program?

The output is a palindrome.
The output is not a palindrome.

I wouldn't know what this program is trying to tell me.

Consider this alternative:

void print_result(char * s)
{
    printf("The characters of \"%s\" %s be rearranged into a palindrome.\n", s, pal_perm(s) ? "can" : "cannot");
}

int main()
{
    print_result("abbas");
    print_result("deeds");
    print_result("dead");
}

Output:

The characters of "abbas" can be rearranged into a palindrome.
The characters of "deeds" can be rearranged into a palindrome.
The characters of "dead" cannot be rearranged into a palindrome.

Though actually I would prefer something much simpler than that:

printf("\"%s\" -> %s\n", s, pal_perm(s) ? "true" : "false");

Producing output:

"abbas" -> true
"deeds" -> true
"dead" -> false

Usability

It would be more interesting if the program took the strings from the command line, instead of using hardcoded values, for example:

int main(int argc, char ** argv) {   
    for (int i = 1; i < argc; i++) {
        print_result(argv[i]);
    }
}

For the record, @Law29 suggested another alternative in a comment:

You can also read from standard input. This lets you either type in words as they come to mind, or use a whole file (there are files of dictionary words, for example). Example:

#define MAX_WORD_SIZE 50
int main(int argc, char ** argv) {   
    char buf[MAX_WORD_SIZE]
    while (fgets (buf, MAX_WORD_SIZE, stdin)) {
        print_result(buf);
    }
}

Testing

Getting the implementation right can be tricky. You revised your post 3-4 times to fix bugs pointed out in comments. It's good to automate your tests so that they can be repeated easily, for example by adding methods like these:

void check(char * s, bool expected)
{
    if (pal_perm(s) != expected) {
        printf("expected \"%s\" -> %s but got %s\n", s, expected ? "true" : "false", expected ? "false" : "true");
        exit(1);
    }
}

void run_tests()
{
    check("a", true);
    check("aa", true);
    check("aba", true);
    check("abba", true);
    check("aabb", true);
    check("aabbs", true);
    check("deeds", true);

    check("ab", false);
    check("abc", false);
    check("dead", false);
}

Use boolean expressions directly

Instead of this:

if(oddCount <= 1)
    return true;
else
    return false;

You can simply return the boolean expression itself:

return oddCount <= 1;

Excessive looping

As @DarthGizka explained, instead of this:

for(char ch = 'a'; ch <= 'z'; ch++)
{
    for(int i=0; i < size; i++)
    {
        if(str[i] == ch)
            alpha[str[i]]++;
    }
}

This is identical, but without unnecessary looping:

for(int i=0; i < size; i++)
{
    alpha[str[i]]++;
}

Unnecessary conditions

The first condition is unnecessary:

    if(alpha[j] == 1 || (alpha[j]%2==1))

This is exactly the same:

    if(alpha[j]%2==1)

Too compact writing style

Instead of this:

    if(alpha[j]%2==1)

I suggest to put spaces around operators, and before ( in if statements:

    if (alpha[j] % 2 == 1)

Stop iterating when you already know the result

Once you find two characters with odd number of occurrences, you can stop iterating and return false. As such, you don't even need an int oddCount, but a bool seenOdd. So instead of this:

int oddCount = 0;

//count the number of times a letter only appears once
for (int j = 0; j < 256; j++)
{
    if (alpha[j] % 2 == 1) oddCount++;
}
//if there is more than one letter that only occurs, then it 
//cannot be a palindrome.
return oddCount <= 1;

You could write:

bool seenOdd = false;

// scan for odd number of occurrences, stop after seeing two
for (int j = 0; j < 256; j++)
{
    if (alpha[j] % 2 == 1) {
        if (seenOdd) return false;
        seenOdd = true;
    }
}

// less then 2 letters with odd number of occurrences, must be true
return true;
| improve this answer | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You can also read from standard input. This lets you either type in words as they come to mind, or use a whole file (there are files of dictionary words, for example). Example: #define MAX_WORD_SIZE 50 int main(int argc, char ** argv) { char buf[MAX_WORD_SIZE]; while (fgets (buf, MAX_WORD_SIZE, stdin)) { print_result(buf); } } \$\endgroup\$ – Law29 Dec 29 '15 at 17:49
  • 2
    \$\begingroup\$ alpha[str[i]] can be a problem if str[i] is negative. Changing the definition of str to unsigned char *str would avoid that problem. \$\endgroup\$ – kasperd Dec 29 '15 at 18:35
  • \$\begingroup\$ @janos, I also had one quick question. Is it better convention to make the name of a method as is_method or isMethod? \$\endgroup\$ – Jonathan Dec 30 '15 at 8:46
6
\$\begingroup\$

Your code scans the string much more often than necessary. Also, iterating over a hard-coded range of characters (from 'a' to 'z') is not only superfluous, it will cause your code to fail when characters outside that range appear.

A string can be rearranged to make a palindrome iff it contains no more than one character with an odd occurrence count. Single-character strings can be excluded with a trivial test if so desired.

Hence the idea is to iterate over the characters in the string to count their occurrences, and to see how many of them have an odd number of occurrences.

The only thing that matters about the occurrence count for a character is whether it is odd or not. This means that things are still okay if you count modulo some convenient modulus, like 256 (leading to byte-sized counters) or 2 (leading to an array of booleans or a bit array).

However, fixed-size arrays can become really awkward (i.e. big) unless the range of allowable characters is tightly bounded, for example restricted to 7-bit ASCII characters. The reason is that Unicode has untold millions of character code points, and creating a fixed-size counter array to accommodate them all takes lots of memory even if you use only a single bit per counter.

Hence, either restrict the range of allowable characters, or use a dynamic mapping mechanism so that you only have to deal with the characters that actually occur in the string.

Thus the recommended plan for an optimised version of your code is this:

  • make a single pass over the input string to count character occurrences
  • make a single pass over the occurrence counters to see if there's more than one odd count
| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ Hello, can you please give me further clarification on dynamically mapping? \$\endgroup\$ – Jonathan Dec 30 '15 at 8:40
  • \$\begingroup\$ A dynamic map can associate arbitrary keys (e.g. strings) with values, unlike the fixed mapping implied by a plain array where key == index. It shouldn't be necessary here since most systems have 8-bit characters. However, systems with CHAR_BIT == 32 can throw monkey wrenches into all kinds of unwarranted assumptions. In C++ you could use a std::map<wchar_t, unsigned>; updating the count for character c would then read ++counts[c] just as if it were an array (since missing entries are added under the hood with a count of 0). At the end there would be entries for all chars that did occur. \$\endgroup\$ – DarthGizka Dec 30 '15 at 11:27
3
\$\begingroup\$

In this alternative

    (alpha[j] == 1 || (alpha[j]%2==1))

if the first part is true, then the second one is true, too, so there's no need to keep them both — just use

    if(alpha[j] % 2)
        oddCount++;

or, a bit faster,

    oddCount += alpha[j] % 2;

This could be made even faster thanks to observation you don't actually need a count of each character, but only the information if the count is even or odd. Then you can replace the counter array char alpha[] with a flag array, and just flip the flag when necessary instead of incrementing. Finally you just count the odd characters:

    int  charodd[256];
    memset(charodd, 0, sizeof charodd);

    int size = strlen(str);
    for(int i=0; i<size; i++)
    {
        unsigned int j = (unsigned char)str[i];

        charodd[j] = ! charodd[j];
    }

    int oddCount = 0;
    for(int j=0; j<256; j++)
    {
        oddCount += charodd[j];
    }
| improve this answer | | | | |
\$\endgroup\$
  • 1
    \$\begingroup\$ You can go even faster by keeping the count while iterating over the string: if (charodd[j] = !charodd[j]) oddCount++; else oddCount--;. (if average string length is < 256) \$\endgroup\$ – Stephan Leclercq Dec 29 '15 at 12:52
  • 1
    \$\begingroup\$ @StephanLeclercq That's right, although compilers comply about assignment in if, so it'd better to add an explicit comparision to zero if ((charodd[j] = !charodd[j]) != 0) {...} or build a comma expression if (charodd[j] = !charodd[j], charodd[j]) {...} \$\endgroup\$ – CiaPan Dec 29 '15 at 20:10
0
\$\begingroup\$

My am giving 2 solutions. IDEA => There must be 1 or no odd element in the String. Therefore we will do a check ch %2 == 1 then it will be a palindrome or else not.

Solution1: Java(using HashSet)

//Check if a given string is a rotation of a palindrome
public class test7 {

    public static void main(String[] args) {
        String s = "Protijayi";

        Set<Character> set = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (set.contains(ch)) {
                set.remove(ch);

            } // if
            else {
                set.add(ch);
            }
        } // for

        if (set.size() <= 1) {
            System.out.println("can be converted into a palindrome");
        } else {
            System.out.println("cannot be a palindrome");
        }

    }
}

In Python : we will do a list comprehension using Counter and we will count how many odd numbers are there.

from collections import Counter


def fix(a):
    return len([  v for v in Counter(a).values() if v % 2 == 1]) <= 1


a = "mmdaa"
print(fix(a))
| improve this answer | | | | |
\$\endgroup\$
  • \$\begingroup\$ You have presented an alternative solution, but haven't reviewed the code. Please edit it to explain your reasoning (how your solution works and how it improves upon the original) so that everyone can learn from your thought process. \$\endgroup\$ – Toby Speight May 2 '18 at 12:12
0
\$\begingroup\$

Accept string literals

I get this warning when I compile:

115308.c:9:56: warning: passing argument 1 of ‘pal_perm’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
     printf("The output is %sa palindrome.\n", pal_perm("abbas")? "": "not "); //Output: The output is a palindrome.
                                                        ^~~~~~~
115308.c:6:15: note: expected ‘char *’ but argument is of type ‘const char *’
 bool pal_perm(char*);
               ^~~~~

That's easily fixed by declaring the function to accept const char*:

bool pal_perm(const char*);

Don't index arrays using char

char may be a signed type, so it's a poor choice here:

        if (str[i] == ch)
            alpha[str[i]]++;

We need to convert str[i] to unsigned char to be safe.

Don't assume a particular range for unsigned char

The standard library gives us UCHAR_MAX, so we should use that when creating our array:

char alpha[UCHAR_MAX + 1];

And when populating it:

for (int j = 0;  j <= UCHAR_MAX;  ++j)

Don't overflow signed types

char is a poor choice for these counters - if there are more than CHAR_MAX of any given character in the input, then the code is undefined. If we use an unsigned type instead, then we can increment it safely. (Though, as other answers suggest, we don't need to count, as we're only interested in the parity of each element.)

Use standard character classification functions

Include <ctype.h> to get isalpha(), which is a more accurate (and locale-adaptive) replacement for your a..z test.

Make a single pass over the string

We don't need to measure the string length with strlen() (but if we did, we should use size_t rather than int to store the result). Instead, we can simply traverse until we see a NUL character. And we can use our copy of the pointer passed in to the function, since we won't need it again:

bool alpha[UCHAR_MAX + 1] = {0};

while (*str) {
    unsigned char c = (unsigned char)*str;
    if (isalpha(c)) {
        alpha[c] = !alpha[c];
    }
    ++str;
}

Accept inputs from command-line

Instead of hard-coding the strings to test, allow them to be provided by the user. Here's an example:

int main(int argc, char **argv)
{
    const char *const message[] = {
        "'%s' cannot be rearranged to a palindrome\n" ,
        "'%s' has at least one palindromic permutation\n"
    };

    for (int i = 1;  i < argc;  ++i) {
        const char *const s = argv[i];
        printf(message[pal_perm(s)], s);
    }
}

I've changed the printing so that it's not "Lego constructed" by bolting together phrases. The latter approach can be hard to translate, compared with the former.


Modified code

#include <ctype.h>
#include <limits.h>
#include <stdio.h>
#include <stdbool.h>

bool pal_perm(const char* str)
{
    bool unpaired[UCHAR_MAX + 1] = {0};

    while (*str) {
        unsigned char c = (unsigned char)*str;
        if (isalpha(c)) {
            unpaired[c] = !unpaired[c];
        }
        ++str;
    }

    // count the number of letters that are not paired
    int oddCount = 0;
    for (int i = 0; i < UCHAR_MAX;  ++i)
    {
        if ((oddCount += unpaired[i]) > 1)
            return false;
    }

    // if we got here, there's at most 1 unmatched letter
    return true;
}

int main(int argc, char **argv)
{
    const char *const message[] = {
        "'%s' cannot be rearranged to a palindrome\n" ,
        "'%s' has at least one palindromic permutation\n"
    };

    for (int i = 1;  i < argc;  ++i) {
        const char *const s = argv[i];
        printf(message[pal_perm(s)], s);
    }
}
| improve this answer | | | | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.