Write a function that compares two strings and returns a third string containing only the letters that appear in both

Question

Hi All,

I got this homework. And have solved it in following way. I need your comments whether it is a good approach or I need to use any other data sturcture to solve it in better way.

    public string ReturnCommon(string firstString, string scndString)
    {
        StringBuilder newStb = new StringBuilder();
        if (firstString != null && scndString != null)
        {
            foreach (char ichar in firstString)
            {
                if (!newStb.ToString().Contains(ichar) && scndString.Contains(ichar))
                    newStb.Append(ichar);
            }
        }
        return newStb.ToString();
    }

Answer 1

Looks OK to me, but for god sakes man - use some descriptive variable names!!

Answer 2

That's fine for a first approach, but you can make a few improvements, and there's a small error.

• If b contains a character in a that's already in c, you'll repeat it.
• To avoid repeats, you might consider using a Set to store the characters, since a Set won't have repeats.
• Assembling strings with += concatenation is usually inefficient; consider using a StringBuilder or an analogous string-assembly class.
• Your variable names aren't very descriptive.
• If a or b are empty, you don't have to do any work at all! Just return an empty string.

You can think about some more sophisticated improvements, too, by imagining how your algorithm scales if you started to use huge strings. For example, one approach might be that if one string is much longer than the other, you can sort the longer one and remove duplicates. Then you can do a binary search on the characters of the shorter string very quickly.

Answer 3

Seems fine. You could do a pair of optimizations depending on the language you are using:

• you can collect the letters of b into some ordered structure (to make the search for it faster), and if it doesn't repeat... better (a set).
• you can use some kind of StrignBuilder (if it's Java or .Net) to not recreate a string with each concatenation inside the loop

Anyway this are optimizations that are good for large, large strings... so, I don't know if their apropiate to your use, or to the intended homework.

Answer 4

Depends on how long are the input strings, what is the letter and how output should look (duplicates) there are a few other approaches.

For example:

If letters are just [A-Z] characters and each letter should appear only once in output string you can build separate string (or table of chars) 'ABC...XZ' (let's call it letters) and run for each loop over letters and check both input strings against each letter from letters.

This gives 26 loop iterations and no more then 52 calls of Contains() method for each input strings -- no matter how long input strings are.

Answer 5

For an alternative solution, you can view the strings as enumerables and use Intersect() like this:

    public static string Common(string first, string second)
    {
        return new string((first.Intersect(second)).ToArray());
    }

Answer 6

To improve on John Feminella's last suggestion, quicker than a binary search (for any sufficiently long string) would be a lookup in a hashset; or a lookup in a 256-element array of booleans, if those are ASCII or UTF8 characters instead of UTF16 characters.

• Instantiate an empty hashset, or an empty array of booleans; name this variable found.
• For each char in the first string, either add the char to the hashset (but beware of duplicate characters in the first string), or set the corresponding element in the found array to true; this will take linear O(n) time.
• For each char in the second string, test whether the char exists in the hashset or whether the corresponding element in the 'found' array is true: if found then add the character to the return string, and also remove the character from the hashset or the clear the boolean element in the array, so that it won't be found again (to beware of duplicate characters in the second string); this will take linear O(n) time.

Answer 7

void get_common_letters_as_string( char *string_one, char *string_two, char **string_common )
{
  char
    *a,
    *b,
    *c;

  *string_common = malloc( strlen(string_one) + strlen(string_two) + 1 );

  qsort( string_one, strlen(string_one), sizeof(char), compare_function );
  qsort( string_two, strlen(string_two), sizeof(char), compare_function );

  a = string_one;
  b = string_two;
  c = *string_common;

  // BX : loop over all string_one    
  while( *a != '\0' )
  {
    // BX : if current char of one and two match, copy to common
    if( *a == *b )
      *c++ = *a;

    // BX : now loop over all matching chars in string two
    while( *a == *b and *b != '\0' )
      b++;

    // BX : now move along one char in string one
    a++;
  }

  *c = '\0';

  return;
}

Answer 8

Using LINQ:

a.ToCharArray().Intersect<char>(b.ToCharArray())

However this is case sensitive.