Check Permutation of Two Strings

From Software Engineers Wiki
Jump to: navigation, search

Check if a string is a permutation of the other.

Answer #1

If a string is a permutation of the other, these two string has same set of characters. Same character may appear multiple times, but it should appear same number of times.

bool isPermutation(std::string super, std::string sub)
{
        int char_count[256] = {};
        const unsigned char *cp;
        int i;

        cp = (const unsigned char *) super.c_str();
        while (*cp != '\0')
                ++char_count[*cp++];

        cp = (const unsigned char *) sub.c_str();
        while (*cp != '\0')
                --char_count[*cp++];

        for (i = 1; i < 256; ++i)
                if (char_count[i] != 0)
                        return false;

        return true;
}

Answer #2

Another way is to sort two strings and compare. If they are permutations, they should result in same string after sorting. This is not an efficient algorithm, but can be done without using extra data structure.

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox