Isomorphic Strings - C Solution

1. Introduction

This post explores the concept of isomorphic strings in C programming. Two strings are considered isomorphic if each character in one string can be replaced to form the other string, with a one-to-one mapping between characters. This problem is a good exercise in string manipulation and hash table usage in C.

Problem

Given two strings s and t, determine if they are isomorphic. For two strings to be isomorphic, all occurrences of a character in s must be replaced with another character (including itself) to get t, maintaining a one-to-one mapping without any overlap.

2. Solution Steps

1. Check if the lengths of s and t are equal. If not, return false.

2. Create two arrays to map the characters of s to t and vice versa.

3. Iterate through the characters of s and t.

4. If a mapping already exists, check if the current characters match the mapping. If not, return false.

5. If no mapping exists, create one.

6. After iterating through all characters, return true if the strings are isomorphic.

3. Code Program

#include <stdio.h>
#include <string.h>

// Function to check if two strings are isomorphic
int isIsomorphic(char* s, char* t) {
    int m1[256] = {0}, m2[256] = {0}, n = strlen(s);

    for (int i = 0; i < n; i++) {
        if (m1[s[i]] != m2[t[i]]) return 0;
        m1[s[i]] = i + 1;
        m2[t[i]] = i + 1;
    }

    return 1;
}

// Main function to test the isIsomorphic function
int main() {
    char s1[] = "egg", t1[] = "add";
    printf("Is Isomorphic (Example 1): %s\n", isIsomorphic(s1, t1) ? "true" : "false");

    char s2[] = "foo", t2[] = "bar";
    printf("Is Isomorphic (Example 2): %s\n", isIsomorphic(s2, t2) ? "true" : "false");

    char s3[] = "paper", t3[] = "title";
    printf("Is Isomorphic (Example 3): %s\n", isIsomorphic(s3, t3) ? "true" : "false");

    return 0;
}

Output:

Is Isomorphic (Example 1): true
Is Isomorphic (Example 2): false
Is Isomorphic (Example 3): true

Explanation:

1. Initialize two mapping arrays m1 and m2.

2. Iterate through each character in s and t.

3. Check if there's a mismatch in the existing character mapping.

4. Update the mapping arrays with the current index for each character.

5. Return true if all characters can be mapped correctly.

6. The main function tests isIsomorphic with three examples and prints whether the strings are isomorphic.