Isomorphic strings in LeetCode

Question

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;

    }
};

Answer 1

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.