205. Isomorphic Strings

LeetCode 205. Isomorphic Strings

Description

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

Two strings s and t 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.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Constraints:

• 1 <= s.length <= 5 * 104

• t.length == s.length

• s and t consist of any valid ascii character.

Tags

Hash Table

Solution

We build the Bijection between two characters at the same index of s and t respectively with 2 maps. If any conflict occurs at index i (s2t[s[i]] != t[i] or t2s[t[i]] != s[i]), we return false immediately. Finally, return true.

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(1)$

Code

func isIsomorphic(s string, t string) bool {
	s2t, t2s := map[byte]byte{}, map[byte]byte{}
	for i := range s {
		x, y := s[i], t[i]
		if s2t[x] > 0 && s2t[x] != y || t2s[y] > 0 && t2s[y] != x {
			return false
		}
		s2t[x], t2s[y] = y, x
	}
	return true
}

Reference

1. 同构字符串

2. 290. Word Pattern