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

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 !开发者_如何学Python= null && scndString != null)
        {
            foreach (char ichar in firstString)
            {
                if (!newStb.ToString().Contains(ichar) && scndString.Contains(ichar))
                    newStb.Append(ichar);
            }
        }
        return newStb.ToString();
    }

---

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());
    }

---

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.

---

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.

---

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.

---

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.

---

Using LINQ:

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

However this is case sensitive.

---

FYI: Here is the C/C++ code:

/* Q: Write a function f(a, b) which takes two character string arguments
      and returns a string containing only the characters found in both
      strings in the order of a. */

#include <iostream>
#include <string>
#include <cstring>
#include <map>
using namespace std;

/* A: Unclear: repeated chars in string a? */
string CommonChars(const char* a, const char* b)
{
    string result("");

    if (!a || !b || !*a || !*b)
        return result;

    map<char, bool> hash;
    int len1 = strlen(a), len2 = strlen(b);

    for (int i = 0; i < len2; ++i)
        hash[b[i]] = true;

    for (int i = 0; i < len1; ++i)
    {
        map<char, bool>::iterator it = hash.find(a[i]);
        if (it != hash.end() && it->second)
        {
            result += a[i];
            hash[a[i]] = false; // OR:  hash.erase(it);
        }
    }

    return result;
}

int main()
{
    cout << CommonChars("abcdefgbx", "gcfcba") << endl;

    return 0;
}
/* Output:
abcfg
 */

---

Here my solution in python. If I am not wrong it should take linear O(n) time.

# Write a function f(a, b) which takes two character string arguments
# and returns a string containing only the characters found in both
# strings in the order of a. 
first_string = "attempt" 
second_string="tmay" #second string
result = []

#it's O(n) operation
for char in first_string:
   if char in second_string:
      if char not in result:
         result.append(char)

print result

results looks like this:

['a', 't', 'm']

---

Create a function that takes two strings as arguments and returns the number of times the first string (the single character) is found in the second string.

function charCount(myChar, str) {
    let newstr = str.split(myChar).length-1;
    return newstr;
}

---

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