rupngr

 Profile Answers by rupngr Questions by rupngr

• Jun 9th, 2008

 

start
Input String str1 and str2 and strFinal
Declare var chrTemp as char
Set chrTemp=str1[0]

while( str1!=""|| str2!="")

check for every char in str1 if it is equal to chrTemp

if it is equal replace it with empty chr ''

check for every char in str2 if it equal to chrTemp

if it is equal replace it with empty chr''

set strFinal=strFinal+chrTemp;
set chrTemp=str1[0]

Loop

if str1!=""  then  set strFinal=strFinal+str1
if str2!=""  then  set strFinal=strFinal+str2

display strFinal as output
stop

guitarfox

 Profile Answers by guitarfox 

• Jun 19th, 2008

 

Implement an algorithm that takes two strings as input, and returns the intersection of the two, with each letter represented at most once. Speed it up and test it.

Assuming that the two strings are not sorted, but they could be sorted by ASCII coding or other means.

Let A and B denote two strings.

If the strings are not sorted, then the search of A[i], 0 <= i < |A|, will take |B| unit of time long.  Which means this algorithm cannot be faster than O(|A| * |B| )

However, by using an appropriate sorting algorithm, (e.g: quick sort, built-in in C) the search time could be reduced dramatically.

To find the intersection, one begins by comparing the head elements of the two strings.  Here is the pseudo code.

i = 0;
j = 0;
k = 0;
while( i < |A| && j < |B| )
{
  if( A[i] == B[i] )
   {
       Results[k] = A[i];
       ++k;
        advance(A, i);
        advance(B, j);
   }
   //  Assuming the strings are sorted in incrementing order

   if( A[i] > B[i] )
    {
        advance(B, j);
    }
    else /* B[i] > A[i] */
   {
         advance(B, i);
   }
}
return Results

void advance(string& Str, int& idx)
{
     /* Just to advance the pointer beyond the consecutive repeated letters. */
     while( Str[idx] == Str[idx+1] ) idx++;
}

In this algorithm I proposed, running time is O( |A| + |B| + |A| log |A| + |B| log |B| ),
or O( n log n), somewhere around that.

If you still want an even faster algorithm, use a hash.

Hash A into a map, and then search for B. 

Depending on the hash function and table size, if the collision was minimized, the running time could be as good as O ( |A| + |B| )

The only concern is the insertion time when hashing A into the map.  Probably a bookkeeping variable is required somewhere for the look-up of letters in B, but that's a secondary concern.

cyrano_says

 Profile Answers by cyrano_says 

• Jul 6th, 2008

 

You can store the ascii values of the characters of the smaller sting in an array and compare the characters of string 2 with this to find the intersection

Murali Mohan

 Profile Answers by Murali Mohan 

• Jul 17th, 2008

 

Using the longer string, build a binary tree with characters as keys. Make a pass through the other smaller string, removing those elements from the binary tree which are not present in the smaller string. The resultant tree obtained will be having the interestion of characters in both the strings and it would be done in O(mlgn) worst case, where m is the length of the smaller string and n is the length of the longer string.

theja123

 Profile Answers by theja123 

• Mar 25th, 2009

 

Create 3 int array of size 26 initialized to zero, scan the first string, and set the corresponding index in first array.
Similarly do for the second.
Now and (&&) the two int array's into third int array.
Create string based on the third array. is result
No comparisons, no sorting, just extra space of 26*3
Speed, amazingly fast 0(n).
Can any one try for o(logn)?

brijpal

 Profile Answers by brijpal 

• Jun 14th, 2009

 

Here is the program exuted in O(m+n) steps where m and n are length of the two strings. It also take an extra space of 256.

public static String intersection(String str1, String str2){
        char[] charArray = new char[256];
        for (int i = 0; i < str1.length(); i++) {
            int index = str1.charAt(i);
            charArray[index] = str1.charAt(i);
        }
        char[] output = new char[256];
        int len = 0;
        for (int i = 0; i < str2.length(); i++) {
            int index = str2.charAt(i);
            if(charArray[index] == str2.charAt(i)){
                output[len++] = str2.charAt(i);
                charArray[index] = 0;
            }
        }
        return new String(output,0,len);
    }

yzesong

 Profile Answers by yzesong 

• Aug 8th, 2009

 

I think of an idea to do this by using a hash table.

First, loop through first string, creat map<char, int>, we can use ascii value of the char as the value. Only insert the char/int pair when a char can not be found in the hash table.

After first string is done, then loop through string2, display the char only if it is found in the hash table, then erase that pair from the map, so any duplicated chars in string2 will not be found again. The displayed chars are the intersection of the two strings, and there will be no duplicated chars.

kaushurtz

 Profile Answers by kaushurtz 

• Mar 2nd, 2010

 

Using HashSet as in case of jave will be better than HashMap. We can just iterate over the characters of both the strings and put them in set.