I often see that candidates use one dictionary when solving leetcode problem #205 ‘Isomorphic Strings’.
There are a lot of submissions in leetcode discussions, they are something like this:
public bool IsIsomorphic(string s, string t)
var dict = new Dictionary<char,char>();
for(int i = 0; i < s.Length; i++)
if (dict.ContainsKey(s[i]) && dict[s[i]]!=t[i])
if (dict.ContainsValue(t[i]) && !dict.ContainsKey(s[i]))
Main idea for that approach is: try to add current s[i],t[i] to dictionary. If dictionary already has a transformation with the same key (equals to s[i]) but different value (not equals to t[i]), we return false. Same if dictionary contains a transformation with the same value (which equals to t[i]) but with different key (not s[i]) — return ‘false’. If dictionary doesn’t contain current pair — we will add it to dictionary.
Looks clear and concise, right?
But I noticed that every person who posts such solutions didn’t post estimates for time and space complexity. Can you guess what the time complexity for the code above is?
It’s square time!
Look at the line with .ContainsValue inside the loop. Typical dictionary operation (Add, ContainsKey, etc.) requires constant time, but ContainsValue is an operation that requires linear time, see off. doc if you doubt. And inside the loop, this gives O(N²) in total.
These two solutions give constant time and space complexity, so when you meet this problem again — do not try to save space, because both one dictionary and two dictionaries gives you the same space complexity.
And do not forget to think about time and space complexity for every problem. When I solve leetcode problems on my streams I try to do this for each solution.