Last active
January 20, 2018 06:53
-
-
Save Isa-rentacs/3744095218ee892031153ad14ede3dec to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdlib.h> | |
void diffOfSets(char* setA, int lenA, char* setB, int lenB, char** setDiff, int* lenDiff) | |
{ | |
int *countDiff = malloc(sizeof(int) * 26); | |
int *isIncludedArray = malloc(sizeof(int) * lenA); | |
int includedItemCount = 0; | |
for(int i=0;i<26;++i) | |
{ | |
countDiff[i] = 0; | |
} | |
for(int i=0;i<lenA;++i) | |
{ | |
countDiff[setA[i] - 'a']++; | |
} | |
for(int i=0;i<lenB;++i) | |
{ | |
countDiff[setB[i] - 'a']--; | |
} | |
for(int i=0;i<26;++i) | |
{ | |
if(countDiff[i] > 0) | |
{ | |
includedItemCount++; | |
} | |
} | |
*setDiff = (char *)malloc(sizeof(char) * includedItemCount); | |
int addedItemCount = 0; | |
for(int i=0;i<26;++i) | |
{ | |
if(countDiff[i] > 0) | |
{ | |
(*setDiff)[addedItemCount] = i + 'a'; | |
addedItemCount++; | |
} | |
} | |
*lenDiff = includedItemCount; | |
/* O(mn) solution | |
for(int i=0;i<lenA;++i) | |
{ | |
int isIncluded = 1; | |
printf("i = %d\n", i); | |
for(int j=0;j<lenB;++j) | |
{ | |
printf("j = %d\n", j); | |
if(setA[i] == setB[j]) | |
{ | |
isIncluded = 0; | |
break; | |
} | |
} | |
if(isIncluded == 1) | |
{ | |
isIncludedArray[i] = 1; | |
includedItemCount++; | |
} | |
} | |
*setDiff = (char *)malloc(sizeof(char) * includedItemCount); | |
int addedItemCount = 0; | |
for(int i=0;i<lenA;++i) | |
{ | |
if(isIncludedArray[i] == 1) | |
{ | |
(*setDiff)[addedItemCount] = setA[i]; | |
addedItemCount++; | |
} | |
} | |
*lenDiff = includedItemCount; | |
*/ | |
} | |
int main(void) { | |
char* ansArray; | |
int ansCount; | |
char A[] = {'z', 'c', 'f'}; | |
int countA = 3; | |
char B[] = {'a', 'b', 'e', 'z'}; | |
int countB = 4; | |
printf("ansArray = %x\n", ansArray); | |
diffOfSets(A, countA, B, countB, &ansArray, &ansCount); | |
for(int i=0;i<ansCount;++i) | |
{ | |
printf("%c", ansArray[i]); | |
} | |
printf("\n"); | |
printf("%d\n", ansCount); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment