Question

Formatted question description: https://leetcode.ca/all/205.html

 205	Isomorphic Strings

 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.

Algorithm

Two HashMaps are used to record the occurrence of characters in the original string and the target string. Since the ASCII code has only 256 characters, a 256-size array can be used to replace the HashMap and initialize it to 0 to traverse the original string.

Take a character from the source string and the target string, and then look up its value in the two arrays respectively. If they are not equal, return false. If they are equal, update its value to i + 1.

Code

import java.util.Arrays;

public class Isomorphic_Strings {

    class Solution {
        public boolean isIsomorphic(String s, String t) {

            if (s == null || t == null || s.length() != t.length()) {
                return false;
            }

            int[] sLastSeen = new int[256];
            int[] tLastSeen = new int[256];

            Arrays.fill(sLastSeen, -1);
            Arrays.fill(tLastSeen, -1);

            for (int i = 0; i < s.length(); i++) {
                char sChar = s.charAt(i);
                char tChar = t.charAt(i);

                // @note: either is >0. including case one is >0 the other is <0
                if (sLastSeen[sChar] >= 0 || tLastSeen[tChar] >= 0) {
                    if (sLastSeen[sChar] != tLastSeen[tChar]) {
                        return false;
                    }
                }

                sLastSeen[sChar] = i;
                tLastSeen[tChar] = i;
            }

            return true;
        }
    }
}

############

class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] d1 = new int[256];
        int[] d2 = new int[256];
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            char a = s.charAt(i), b = t.charAt(i);
            if (d1[a] != d2[b]) {
                return false;
            }
            d1[a] = i + 1;
            d2[b] = i + 1;
        }
        return true;
    }
}

// OJ: https://leetcode.com/problems/isomorphic-strings/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        unordered_map<char, char> m, r;
        for (int i = 0; i < s.size(); ++i) {
            if (m.count(s[i]) && m[s[i]] != t[i]) return false;
            if (r.count(t[i]) && r[t[i]] != s[i]) return false;
            m[s[i]] = t[i];
            r[t[i]] = s[i];
        }
        return true;
    }
};

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        d1, d2 = [0] * 256, [0] * 256
        for i, (a, b) in enumerate(zip(s, t)):
            a, b = ord(a), ord(b)
            if d1[a] != d2[b]:
                return False
            d1[a] = d2[b] = i + 1
        return True

############

class Solution(object):
  def isIsomorphic(self, s, t):
    """
    :type s: str
    :type t: str
    :rtype: bool
    """
    return len(set(s)) == len(set(t)) == len(set(zip(s, t)))

func isIsomorphic(s string, t string) bool {
	d1, d2 := make([]int, 256), make([]int, 256)
	for i, a := range s {
		b := t[i]
		if d1[a] != d2[b] {
			return false
		}
		d1[a], d2[b] = i+1, i+1
	}
	return true
}

function isIsomorphic(s: string, t: string): boolean {
    const n = s.length;
    const help = (s: string, t: string) => {
        const map = new Map();
        for (let i = 0; i < n; i++) {
            if (map.has(s[i])) {
                if (map.get(s[i]) !== t[i]) {
                    return false;
                }
            } else {
                map.set(s[i], t[i]);
            }
        }
        return true;
    };
    return help(s, t) && help(t, s);
}

public class Solution {
    public bool IsIsomorphic(string s, string t) {
        var d1 = new Dictionary<char, char>();
        var d2 = new Dictionary<char, char>();
        for (var i = 0; i < s.Length; ++i)
        {
            char mapping1;
            char mapping2;
            var found1 = d1.TryGetValue(s[i], out mapping1);
            var found2 = d2.TryGetValue(t[i], out mapping2);
            if (found1 ^ found2) return false;
            if (!found1)
            {
                d1.Add(s[i], t[i]);
                d2.Add(t[i], s[i]);
            }
            else if (mapping1 != t[i] || mapping2 != s[i])
            {
                return false;
            }
        }
        return true;
    }
}

use std::collections::HashMap;
impl Solution {
    fn help(s: &[u8], t: &[u8]) -> bool {
        let mut map = HashMap::new();
        for i in 0..s.len() {
            if map.contains_key(&s[i]) {
                if map.get(&s[i]).unwrap() != &t[i] {
                    return false;
                }
            } else {
                map.insert(s[i], t[i]);
            }
        }
        true
    }

    pub fn is_isomorphic(s: String, t: String) -> bool {
        let (s, t) = (s.as_bytes(), t.as_bytes());
        Self::help(s, t) && Self::help(t, s)
    }
}

205 - Isomorphic Strings

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions