CTCI 系列 --1.3 判断两个字符串是否互为变换（C 语言）

题目：Given two strings,write a method to decide if one is a permutation of the other.

对于给定的两个字符串，写一个方法判断其中一个是否是另一个的变换。

解题思路

分析题目，要判断一个字符串是否是另一个字符串变换得来。那么首先，这两个字符串必须==长度相等==；其次两个字符串中的每个字符必须相一致。

那么，我们代码可以这样实现：

• 先判断两个字符串的长度，若不相等则返回 false；若相等进入下一步
• 对两个字符串分别进行排序
• 排序完，使用 memcpy() 函数进行内存对比，如相等则返回 true,不相等则返回 false

代码如下：

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

void swap(char *a, char*b)
{
    *a ^= *b;
    *b ^= *a;
    *a ^= *b;
}

void sort_string(char *str,int len)
{
    int i, j;
    char flag = 0;
    for (i = 0; i < len; i++)
    {
        flag = 0;
        for (j = 1; j < len - i - 1; j++)
        {
            if (str[j] > str[j + 1])
            {
                swap(&str[j], &str[j + 1]);
                flag = 1;
            }
        }

        if (0 == flag)
            break;
    }
}

//返回1 ---- 字符串互为变换 0 ---- 字符串不是
int campara_str(char *str1, char *str2)
{
    int len1=0, len2 = 0;

    len1 = strlen(str1);
    len2 = strlen(str2);

    sort_string(str1, len1);
    sort_string(str2, len2);

    if (memcmp(str1, str2, len1) == 0)
        return 1;
    else
        return 0;
}

int main(void)
{
    char buf1[6];
    char buf2[6];

    memset(buf1, 0, sizeof(buf1));
    memset(buf2, 0, sizeof(buf2));
    strcpy(buf1, "hello");
    strcpy(buf2, "helol");

    if (campara_str(buf1, buf2))
    {
        printf("The two strings is anagram!\n");
    }
    else
    {
        printf("The two strings is not anagram!\n");
    }

    memset(buf2, 0, sizeof(buf2));
    strcpy(buf2, "helio");

    if (campara_str(buf1, buf2))
    {
        printf("The two strings is anagram!\n");
    }
    else
    {
        printf("The two strings is not anagram!\n");
    }

    getchar();

    return 0;
}

PS: 不要直接比较两个静态字符串 campara_str("hello", "helol") ，const 数据是无法修改的，排序时会出错。

运行结果

另一种方法

还有一种方法，就是统计两个字符串中每个字符的出现次数，然后做比较。若出现次数一致则返回 true;否则返回 flase.
算法如下：

int campara_str2(char *str1, char *str2)
{
    int letter1[256],letter2[256];

    memset(letter1, 0, sizeof(letter1));
    memset(letter2, 0, sizeof(letter2));

    while (*str1 != '\0')
    {
        letter1[*str1++]++;
    }

    while (*str2 != '\0')
    {
        letter2[*str2++]++;
    }

    if (memcmp((void *)&letter1, (void *)&letter2, sizeof(letter1)) == 0)
        return 1;
    else
        return 0;
}