LeetCode Entry

205. Isomorphic Strings

02.04.2024 easy 2024 kotlin rust

Can map chars from one string to another?

205. Isomorphic Strings easy blog post substack youtube 2024-04-02_08-59.webp

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/558

Problem TLDR

Can map chars from one string to another? #easy

Intuition

Let’s check if previous mapping is the same, otherwise result is false

Approach

We can use a HashMap or a simple [128] array.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(w)\), w is an alphabet or O(1)

Code


  fun isIsomorphic(s: String, t: String): Boolean {
    val map = mutableMapOf<Char, Char>()
    val map2 = mutableMapOf<Char, Char>()
    for ((i, c) in s.withIndex()) {
      if (map[c] != null && map[c] != t[i]) return false
      map[c] = t[i]
      if (map2[t[i]] != null && map2[t[i]] != c) return false
      map2[t[i]] = c
    }
    return true
  }



  pub fn is_isomorphic(s: String, t: String) -> bool {
    let mut m1 = vec![0; 128]; let mut m2 = m1.clone();
    for i in 0..s.len() {
      let c1 = s.as_bytes()[i] as usize;
      let c2 = t.as_bytes()[i] as usize;
      if m1[c1] > 0 && m1[c1] != c2 { return false }
      if m2[c2] > 0 && m2[c2] != c1 { return false }
      m1[c1] = c2; m2[c2] = c1
    }
    return true
  }