user3605367 user3605367 - 2 months ago 8
C Question

Check if two strings are permutations in C

Im actually trying to make some program who can check if two strings are permutation from each other. I explain :

If I consider :

Eagle


and

Hdjoh


(I used these two examples in a previous question).

I get a permutation, and the permutation parameter is 3. Why ? Because in the alphabet : E + 3 = H, a + 3 = d etc..

I used unsigned char because if I get a z in one of my strings, I want that (for example) z + 3 = c.




What I started to do :

#include <stdio.h>
#define N 20

int my_strlen(unsigned char *string){
int length;
for (length = 0; *string != '\0'; string++){
length++;
}
return(length);
}

int main()
{
unsigned char string1[N], string2[N];
int test=0, i=0, length1, length2;
scanf("%s", string1);
scanf("%s", string2);

length1=my_strlen(string1);
length2=my_strlen(string2);

if(length1==length2){
for(i=0; i<length1; i++){
if(string1[i]==string2[i]){
test=1;
}
else{
test=0;
}
}
printf("Test = %d", test);
}
else{
printf("Error");
}

return 0;
}





I just started to think about it.. So for the moment I just try to compare the two strings letter by letter.

The problem here : If i try to compare Hello and hello, or Hello and Helqo I get Test = 1.

So someone can tell me whats wrong here ?

Thanks a lot.




EDIT 1 :

#include <stdio.h>
#define N 20

int my_strlen(unsigned char *string){
int length;
for (length = 0; *string != '\0'; string++){
length++;
}
return(length);
}

int main()
{
unsigned char string1[N], string2[N];
int test=0, i=0, length1, length2;
scanf("%s", string1);
scanf("%s", string2);

length1=my_strlen(string1);
length2=my_strlen(string2);

if(length1==length2){
for(i=0; i<length1; i++){
if(string1[i]==string2[i]){
test=1;
}
else{
test=0;
break;
}
}
printf("Test = %d", test);
}
else{
printf("Error");
}

return 0;
}


Now it's correct. I will continue.




EDIT 2 - 6.7.14 :

I am actually working and the "second part" of the program. I am looking for the d and I verify if its a permutation or not. No so easy so I need some advices, do I have to write an other function to do this ? Or just working on this part of my code :

if(length1==length2){
for(i=0; i<length1; i++){
if(string1[i]==string2[i]){
test=1;
}
else{
test=0;
break;
}
}
printf("Test = %d", test);
}
else{
printf("Error");
}

return 0;
}


I wrote it like this for the moment :

if(length1==length2){
for(i=0; i<length1; i++){
for(d=0; d<255; d++){
if(string1[i]==string2[i] + d){
permutation=1;
}
else{
permutation=0;
break;
}
}
}
printf("\nPermutation = %d \nd = %d", permutation, d);
}
else{
printf("Not a permutation");
}

return 0;
}


(I know that it doesn't work but I just tried..).

Thanks by advance for the help.

Answer

You can think about the problem like this. For two strings to be a valid permutation, the character distances have to be equal for each character in the strings. So you can check the first character distance and then loop over the other characters and verify that the distance is the same. As soon as it is not equal to first character distance, you can safely conclude that it is not a permutation.

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

int main(void)
{
    int i;
    unsigned char string1[] = "test";
    unsigned char string2[] = "vguv";

    int slength1 = 4;
    int slength2 = 4;

    int distance;
    int is_permutation = 1;

    if (slength1 != slength2) {
        is_permutation = 0;
    }

    distance = (int)string2[0] - (int)string1[0];

    for (i=1; i<slength1; ++i) {
        if ( ((int)string2[i] - (int)string1[i]) != distance ) {
            is_permutation = 0;
            break;
        }
    }

    if (is_permutation) {
        printf("%s is a permutation of %s with distance %d\n", string1, string2, distance);
    } else {
        printf("%s is not a permutation of %s\n", string1, string2);
    }

    return EXIT_SUCCESS;
}

Please note that I have used statically defined strings and stringlengths. Your original way of reading in user input is prone to undefined behaviour. You declare a string of fixed length (20 in the OP) so if a user enters a string longer than 19 the scanf will run out of bounds and invoke undefined behaviour. This is very bad and you should read up on it.

Comments