algoadvance

Leetcode 205. Isomorphic Strings

Problem Statement

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.

Example 1:

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

Example 2:

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

Example 3:

Input: s = "paper", t = "title"
Output: true

Constraints:

• 1 <= s.length <= 5 * 10^4
• t.length == s.length
• s and t consist of any valid ASCII character.

Clarifying Questions

1. Q: Do we consider an empty string to be isomorphic with another empty string? A: Yes, since they trivially satisfy the condition of having no characters to map between the two.

2. Q: Are the strings always of the same length? A: Yes, as per the problem statement t.length == s.length.

3. Q: Can we assume the strings contain only printable ASCII characters? A: Yes, the problem states they consist of any valid ASCII character.

Strategy

1. Character Mapping: Use two hash maps to maintain mapping from s to t and t to s.
2. Validation: As we iterate through the characters of both strings, update both hash maps. If any inconsistency is found (i.e., a character from s maps to a different character in t than expected or vice versa), return false.

Code

import java.util.HashMap;

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) return false;

        HashMap<Character, Character> mapS = new HashMap<>();
        HashMap<Character, Character> mapT = new HashMap<>();
        
        for (int i = 0; i < s.length(); i++) {
            char charS = s.charAt(i);
            char charT = t.charAt(i);
            
            if (mapS.containsKey(charS)) {
                if (mapS.get(charS) != charT) {
                    return false;
                }
            } else {
                mapS.put(charS, charT);
            }
            
            if (mapT.containsKey(charT)) {
                if (mapT.get(charT) != charS) {
                    return false;
                }
            } else {
                mapT.put(charT, charS);
            }
        }
        
        return true;
    }
}

Time Complexity

• Time Complexity: The algorithm runs in O(n) time, where n is the length of the strings. We iterate through each character of the strings exactly once.
• Space Complexity: The space complexity is O(1) since the hash map will at most store a character mapping for all unique characters of the ASCII set, which is constant in size (256 characters).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?