Welcome to Subscribe On Youtube

Question

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

Given two strings s and t, determine if they are isomorphic.

Two strings s and t 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 * 104
  • t.length == s.length
  • s and t consist of any valid ascii character.

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)
        }
    }
    
    

All Problems

All Solutions