Interested to Buy Any Domain ? << Click Here >> for more details...
Answer Posted / om
Input: str1 (size M), str2 (size N)
Output:- Union_string str3.
1. Take a auxillary interger array of size 128 and
initialize all its's enteries to zero.(becoz All printable
chacter has value in the range [0,127]. so 128)
int Aux[128]={0}; //O(128) TIME
2. set Couter = strlen(str1) + strlen(str2) +1 ;//extra one
for '\0' character..
3. now scan the first string str1 and put 1 on the index
value equal to str1[i] in auxillary array.If there were
already 1,then Counter--;
Aux[str1[i]]=1; //O(M) TIME
4. now scan the second string str2 and put 1 on the index
value equal to str2[i] in auxillary array.Similar to step 3.
If there were already 1,then Counter--;
Aux[str2[i]=1; //O(N) TIME
5. Now alloacte a memory of size equal to "Counter" for our
resulting union string str3.
char *str3=(char*)malloc(Counter);
6. now again scan the str1 followed by str2. and if any 1 is
found in Aux[str1[i]] or Aux[str2[i]] make it 0. and put
that character to union string str3.
int k=0;
for(int i=0; str1[i]!='\0' ;i++) //O(M)
if(Aux[str1[i]] ==1)
{
str3[k++]=str1[i];
Aux[str1[i]] =0;
}
for(int i=0; str2[i]!='\0' ;i++) //0(N)
if(Aux[str2[i]] ==1)
{
str3[k++]=str2[i];
Aux[str2[i]] =0;
}
str3[k]=\0';
and return str3.
// SO TOTAL O(MAX(M,N)) TIME COMPLEXITY ALGORITHM USING
CONSTANT SPACE OF SIZE 128.
| Is This Answer Correct ? | 2 Yes | 2 No |
Post New Answer View All Answers
What are the advantages and disadvantages of c language?
Explain threaded binary trees?
What is the mean of function?
what is the difference between north western polytechnique university and your applied colleges?? please give ur answers for this. :)
How was c created?
How to delete a node from linked list w/o using collectons?
Explain bitwise shift operators?
Explain what is the difference between functions getch() and getche()?
Can we assign integer value to char in c?
The performance of an operation in several steps with each step using the output of the preceding step a) recursion b) search c) call by value d) call by reference
What is file in c language?
Are the outer parentheses in return statements really optional?
Which programming language is best for getting job 2020?
What is volatile variable in c with example?
Explain what is the benefit of using #define to declare a constant?
