Isomorphic Strings
Problem 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
Explanation:
The strings s and t can be made identical by:
- Mapping
'e'to'a'. - Mapping
'g'to'd'.
Example 2:
Input: s = "foo", t = "bar"
Output: false
Explanation:
The strings s and t can not be made identical as 'o' needs to be mapped to both 'a' and 'r'.
Example 3:
Input: s = "paper", t = "title"
Output: true
Constraints:
- 1 <= s.length <= 5 * 104
- t.length == s.length
sandtconsist of any valid ascii character.
Solve it on LeetCode
Approaches
1. Brute Force
Intuition:
A brute force approach involves checking character by character and ensuring each character maps to exactly one character. For this, we can use an array to track the mapping of characters.
- For each character in the given strings, map them into a fixed-size array based on ASCII values.
- Check if there is a consistent mapping from characters of
stotandttos.
Code:
- Time Complexity: O(n), where n is the length of the string. We iterate over the string once.
- Space Complexity: O(1). The space used by the arrays is constant due to the fixed size (256).
2. Hash Maps
Intuition:
To better understand the character relationships, we'll use two hash maps. This solution tracks mapping from both s to t and t to s, ensuring a one-to-one and onto mapping.
- Create two hash maps.
- For each character, ensure the mapping is unique and consistent in both directions.
Code:
- Time Complexity: O(n), where n is the length of the string. We iterate through each character once.
- Space Complexity: O(1), specifically O(26) if considering distinct lowercase letters. In practice, the space used by hash maps is relative to the character set.