Welcome to Subscribe On Youtube

205. Isomorphic Strings

Description

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.

Solutions

Solution 1: Hash Table or Array

We can use two hash tables or arrays $d_1$ and $d_2$ to record the character mapping relationship between $s$ and $t$.

Traverse $s$ and $t$, if the corresponding character mapping relationships in $d_1$ and $d_2$ are different, return false, otherwise update the corresponding character mapping relationships in $d_1$ and $d_2$. After the traversal is complete, it means that $s$ and $t$ are isomorphic, and return true.

The time complexity is $O(n)$ and the space complexity is $O(C)$. Where $n$ is the length of the string $s$; and $C$ is the size of the character set, which is $C = 256$ in this problem.

Solution 2

This implementation follows the required operations directly. It traverses the relevant values and updates its state as each value is processed. After all required states have been considered, the maintained result is returned.

• Java
• C++
• Python
• Go
• TypeScript
• C#
• Rust

• 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;
      }
  }
  
  
  // Solution 2
  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;
      }
  }
  
  

• class Solution {
  public:
      bool isIsomorphic(string s, string t) {
          int d1[256]{};
          int d2[256]{};
          int n = s.size();
          for (int i = 0; i < n; ++i) {
              char a = s[i], b = t[i];
              if (d1[a] != d2[b]) {
                  return false;
              }
              d1[a] = d2[b] = i + 1;
          }
          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), 1):
              a, b = ord(a), ord(b)
              if d1[a] != d2[b]:
                  return False
              d1[a] = d2[b] = i
          return True
  
  
  # Solution 2
  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), 1):
              a, b = ord(a), ord(b)
              if d1[a] != d2[b]:
                  return False
              d1[a] = d2[b] = i
          return True
  
  

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

• function isIsomorphic(s: string, t: string): boolean {
      const d1: number[] = new Array(256).fill(0);
      const d2: number[] = new Array(256).fill(0);
      for (let i = 0; i < s.length; ++i) {
          const a = s.charCodeAt(i);
          const b = t.charCodeAt(i);
          if (d1[a] !== d2[b]) {
              return false;
          }
          d1[a] = i + 1;
          d2[b] = i + 1;
      }
      return true;
  }
  
  

• public class Solution {
      public bool IsIsomorphic(string s, string t) {
          int[] d1 = new int[256];
          int[] d2 = new int[256];
          for (int i = 0; i < s.Length; ++i) {
              var a = s[i];
              var b = t[i];
              if (d1[a] != d2[b]) {
                  return false;
              }
              d1[a] = i + 1;
              d2[b] = i + 1;
          }
          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