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
Is null always equal to 0(zero)?
What is the purpose of 'register' keyword in c language?
Are bit fields portable?
Why static is used in c?
What is static memory allocation?
Draw a flowchart to produce a printed list of all the students over the age of 20 in a class .The input records contains the name and age of students. Assume a sentinel value of 99 for the age field of the trailer record
Write a program to print numbers from 1 to 100 without using loop in c?
What is the difference between far and near in c?
What is the difference between abs() and fabs() functions?
What is a example of a variable?
What is a stream in c programming?
Why we use int main and void main?
How to write a code for reverse of string without using string functions?
Differentiate between the = symbol and == symbol?
What is the right type to use for boolean values in c?
