5
\$\begingroup\$

I solved this problem:

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example:

Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:

You may assume both s and t have the same length.

The code in C# on average took around 109ms to execute, which is pretty slow compared to the C++ version of the same algorithm, which executes in under 6ms. Although, the fastest C# solution for this problem is around 100ms.

public class Solution {
    public bool IsIsomorphic(string s, string t) {
            int[] map = Enumerable.Repeat(-1, 175).ToArray();
            bool[] marked = Enumerable.Repeat(false, 175).ToArray();
            for(int i=0; i<s.Length; ++i)
            {
                if (map[s[i]] ==  -1) // Unvisited 
                {
                    if (marked[t[i]]) // Already has a mapping
                    {
                        return false;
                    }

                    marked[t[i]] = true;

                    map[s[i]] = t[i];
                }
                else if(map[s[i]] != t[i])
                {
                    return false;
                }
            }

            return true;
    }
}

Optimizations I had done:

  • Converted List<T> to array after reading this
  • Changed foreach to a plain for loop that helped remove another index variable for iterating over string t

Can you suggest any better way to squeeze some performance from the C# implementation?

And from the FAQ section of LeetCode I could see that C# uses mono 4.2.1 and C++ uses g++ 5.4.0.

I'm attaching the C++ solution as well just for reference:

#define MAX_CHARS 175
class Solution {
public:
    bool isIsomorphic(string str1, string str2) {
    bool marked[MAX_CHARS] = {false};

    // To store mapping of every character from str1 to
    // that of str2. Initialize all entries of map as -1.
    int map[MAX_CHARS];
    memset(map, -1, sizeof(map));

    // Process all characters one by on
    for (int i = 0; i < str1.size(); i++)
    {
        // If current character of str1 is seen first
        // time in it.
        if (map[str1[i]] == -1)
        {
            // If current character of str2 is already
            // seen, one to one mapping not possible
            if (marked[str2[i]] == true)
                return false;

            // Mark current character of str2 as visited
            marked[str2[i]] = true;

            // Store mapping of current characters
            map[str1[i]] = str2[i];
        }

        // If this is not first appearance of current
        // character in str1, then check if previous
        // appearance mapped to same character of str2
        else if (map[str1[i]] != str2[i])
            return false;
    }

    return true;

    }
};
\$\endgroup\$
  • \$\begingroup\$ My execution of Console.WriteLine(IsIsomorphic("paper","title")); took less than 10 ms due to VS 2015 Diagnostic Tools on Windows 10 64 bit Core i7-6820HQ 2.7 GHz. \$\endgroup\$ – Tomáš Paul Nov 27 '16 at 22:12
  • 3
    \$\begingroup\$ C# is a JIT language, the first time through is when it compiles to machine code. It is difficult to compare C# to C++ when the method is only called once. I'm willing to bet that it's a much closer implementation if you run it multiple times and even better in release with the debugger detached. \$\endgroup\$ – Ron Beyer Nov 28 '16 at 2:17
3
\$\begingroup\$

I don't know how much runtime you'll save, but you're iterating 175 more times than you need to here.

int[] map = Enumerable.Repeat(-1, 175).ToArray();
bool[] marked = Enumerable.Repeat(false, 175).ToArray();

You can replace this with an old fashioned for loop and set them both at once.

const int maxChars = 175;

int[] map = new int[maxChars];
bool[] marked = new bool[maxChars];

for (var i = 0; i < maxChars; i++)
{
    map[i] = -1; 
    marked[i] = false;
}

It's more verbose, but might save you a millisecond or 2.

\$\endgroup\$
  • 4
    \$\begingroup\$ There isn't really a good reason to do Enumerable.Repeat(false, 175), by default bool is false already, so bool[] marked = new bool[175]; does the same thing. \$\endgroup\$ – Ron Beyer Nov 28 '16 at 14:56
  • \$\begingroup\$ Nice catch @RonBeyer! \$\endgroup\$ – RubberDuck Nov 28 '16 at 14:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.