algoadvance

Leetcode 205. Isomorphic Strings

Problem Statement

The problem “Isomorphic Strings” can be found at LeetCode (problem 205). Here’s the 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

Note: You may assume both s and t have the same length.

Clarifying Questions

  1. Can the input strings be empty?
    • Yes, the problem implies that the input strings can be empty, and two empty strings are trivially isomorphic.
  2. Are there any constraints on the character set?
    • The problem doesn’t explicitly mention, but typically for such problems, the characters are assumed to be from the ASCII set.
  3. Is case sensitivity a factor?
    • Yes, the comparison should be case-sensitive, meaning ‘A’ and ‘a’ are different characters.

Strategy

To determine if two strings s and t are isomorphic, we will:

  1. Use two hash maps (or dictionaries) to keep track of the mapping from characters in s to characters in t, and from characters in t to characters in s.
  2. Iterate over the characters of both strings simultaneously.
  3. For each character pair (s_char, t_char):
    • If s_char is already mapped to some character in t, we check if it is mapped to t_char.
    • If t_char is already mapped to some character in s, we check if it is mapped to s_char.
    • If there is any inconsistency, return false.
  4. If all characters are consistently mapped, return true.

Code

Here is the C++ implementation of the approach discussed:

#include <unordered_map>
#include <string>

class Solution {
public:
    bool isIsomorphic(std::string s, std::string t) {
        if (s.length() != t.length()) return false;

        std::unordered_map<char, char> s_to_t;
        std::unordered_map<char, char> t_to_s;

        for (size_t i = 0; i < s.length(); ++i) {
            char s_char = s[i];
            char t_char = t[i];

            // Check mapping from s to t
            if (s_to_t.find(s_char) != s_to_t.end()) {
                if (s_to_t[s_char] != t_char) {
                    return false;
                }
            } else {
                s_to_t[s_char] = t_char;
            }

            // Check mapping from t to s
            if (t_to_s.find(t_char) != t_to_s.end()) {
                if (t_to_s[t_char] != s_char) {
                    return false;
                }
            } else {
                t_to_s[t_char] = s_char;
            }
        }

        return true;
    }
};

Time Complexity

The time complexity of this solution is O(n), where n is the length of the strings s and t. This is because we iterate over each character in the strings exactly once, and all operations within the loop (hash map operations) are O(1) on average.

The space complexity is also O(n) due to the storage used by the two hash maps that map characters from s to t and from t to s.

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