NUHMAN.com

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 in s must map to the same character in t, and no two characters in s may map to the same character in t.

Function Signature:

go

func isIsomorphic(s string, t string) bool

Example 1:

go

fmt.Println(isIsomorphic("egg", "add")) // Output: true

Explanation: The characters 'e' and 'g' map to 'a' and 'd', respectively.

Example 2:

go

fmt.Println(isIsomorphic("foo", "bar")) // Output: false

Explanation: The characters 'f' and 'o' in s map to 'b' and 'a' in t, but the second 'o' in s maps to both 'a' and 'r', which is not allowed.

Example 3:

go

fmt.Println(isIsomorphic("paper", "title")) // Output: true

Explanation: The characters 'p', 'a', 'e', and 'r' map to 't', 'i', 'l', and 'e', respectively.

Constraints:

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

Approach

To solve this problem, we need to check if each character in s can be mapped to a unique character in t, and vice versa. This means two mappings need to be valid:

1. Mapping from s to t: Each character in s must map to one unique character in t.
2. Mapping from t to s: Each character in t must map to one unique character in s.

To achieve this:

• We can use two hash maps (or dictionaries) to keep track of the character mappings.
• One hash map will store the mapping from s to t, and another hash map will store the mapping from t to s.

Steps:

1. Iterate through the characters of both strings s and t simultaneously.
2. For each character pair (s[i], t[i]), check if the character in s already has a mapping to a different character in t and vice versa.
3. If any mapping conflict occurs, return false.
4. If all characters are mapped correctly, return true.

Time Complexity:

• O(n), where n is the length of the strings. We make a single pass through the strings.

Go Implementation

go

package main

import "fmt"

// Function to check if two strings are isomorphic
func isIsomorphic(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    // Two maps to store the character mappings
    sToT := make(map[byte]byte)
    tToS := make(map[byte]byte)

    // Iterate through the characters of both strings
    for i := 0; i < len(s); i++ {
        if sToT[s[i]] != 0 && sToT[s[i]] != t[i] {
            return false
        }
        if tToS[t[i]] != 0 && tToS[t[i]] != s[i] {
            return false
        }

        sToT[s[i]] = t[i]
        tToS[t[i]] = s[i]
    }

    return true
}

func main() {
    // Example 1
    fmt.Println(isIsomorphic("egg", "add")) // Output: true

    // Example 2
    fmt.Println(isIsomorphic("foo", "bar")) // Output: false

    // Example 3
    fmt.Println(isIsomorphic("paper", "title")) // Output: true
}

Explanation of the Code:

1. isIsomorphic Function:

• Input: The function takes two strings s and t.
• Edge Case Check: If the lengths of s and t are not equal, they cannot be isomorphic, so we return false.
• Mapping Initialization: We create two maps (sToT and tToS) to store the mappings from characters in s to t and from t to s, respectively.
• Iteration and Mapping Validation:
• For each character pair (s[i], t[i]), we check if the current character in s is already mapped to a different character in t or vice versa.
• If a conflict occurs, we return false. Otherwise, we update the mappings.
• Return True: If we complete the iteration without conflicts, we return true.

2. Main Function:

• The main function tests the isIsomorphic function with a few sample test cases.

Example Walkthrough

Example 1:

Input:

go

fmt.Println(isIsomorphic("egg", "add"))

• The mapping for s = "egg" and t = "add" is:
• 'e' maps to 'a'
• 'g' maps to 'd'
• All characters are mapped correctly, so the function should return true.

Output: true

Example 2:

Input:

go

fmt.Println(isIsomorphic("foo", "bar"))

• The mapping for s = "foo" and t = "bar" is:
• 'f' maps to 'b'
• 'o' maps to 'a'
• The second 'o' in s would map to both 'a' and 'r', causing a conflict.
• The function should return false.

Output: false

Example 3:

Input:

go

fmt.Println(isIsomorphic("paper", "title"))

• The mapping for s = "paper" and t = "title" is:
• 'p' maps to 't'
• 'a' maps to 'i'
• 'e' maps to 'l'
• 'r' maps to 'e'
• All characters are mapped correctly, so the function should return true.

Output: true

Conclusion

The LeetCode 205: Isomorphic Strings problem is efficiently solved using two hash maps to track the character mappings between the strings. This solution ensures that we check both mappings from s to t and from t to s, ensuring a valid isomorphism.

This approach runs in O(n) time, where n is the length of the strings, which is optimal for this problem.