# Isomorphic strings in LeetCode

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 "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;
}
}


• 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;

}
};

• 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. – Tomáš Paul Nov 27 '16 at 22:12
• 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. – Ron Beyer Nov 28 '16 at 2:17

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.

• 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. – Ron Beyer Nov 28 '16 at 14:56
• Nice catch @RonBeyer! – RubberDuck Nov 28 '16 at 14:57