I solvedthis 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 around109ms to execute, which is pretty slow compared to the C++ version of the same algorithm, which executes in under6ms. Although, the fastest C# solution for this problem is around100ms.

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:

• ConvertedList<T> toarray after readingthis
• Changedforeach to a plainfor loop that helped remove another index variable for iterating over stringt

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 175class 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;    }};

• \$\begingroup\$My execution ofConsole.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\$

  Tomas Paul

  – Tomas Paul

  2016-11-27 22:12:15 +00:00

  CommentedNov 27, 2016 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

  – Ron Beyer

  2016-11-28 02:17:52 +00:00

  CommentedNov 28, 2016 at 2:17

1 Answer1

Start asking to get answers

Find the answer to your question by asking.

Explore related questions

See similar questions with these tags.