Изоморфын мөрүүд Leetcode шийдэл


Хэцүү байдлын түвшин Easy
Байнга асуудаг Adobe Амазоны Apple-ийн Bloomberg Facebook-ийн Google-ийн Intel LinkedIn Microsoft- Oracle-ийн Yahoo
HashMap String

Асуудлын мэдэгдэл

Энэ асуудалд бид хоёрыг өгдөг мөр, a ба b. Бидний зорилго бол хоёр мөр нь изоморф байгаа эсэхийг ялгах явдал юм.

Хоёр мөрийг изоморф гэж нэрлэдэг бөгөөд зөвхөн эхний мөрийн тэмдэгтүүдийг тэмдэгтүүдийн харьцангуй эрэмбийг ижил байлгахын зэрэгцээ үүссэн бүх цэгүүдэд ямар ч тэмдэгтээр (өөрийг нь оруулаад) орлуулж болох юм. Хоёр тэмдэгт ижил тэмдэгт дээр буулгаж чадахгүй.

Жишээ нь

s = "abb"  , t = "cdd"
true
s = "Google" , t = "123456"
false

Изоморфын мөрүүд Leetcode шийдэл

арга барил

Эхний мөрөнд тэмдэгт бүрийн орлуулалтыг хадгалахын тулд бид hashmaps ашиглаж болно. Хэрэв бид эхний дүрийг орлох байр сууринд хүрвэл,

  • Орлуулах нь бусад мөрийн тэмдэгттэй ижил эсэхийг бид шалгаж болно. Хэрэв үгүй ​​бол мөр нь изоморф байж чадахгүй.
  • Эхний тэмдэгтийг солих боломжгүй тохиолдолд бид эхний тэмдэгт дэх бусад тэмдэгтийг орлуулахын тулд хоёр дахь тэмдэгтийг ашигласан эсэхийг шалгаж болно. Эхний мөрөнд байгаа тэмдэгт бүрийг өвөрмөц тэмдэгтээр буулгах шаардлагатай тул энэхүү чек чухал ач холбогдолтой юм. Хэрэв орлуулалт нь хоёр дахь тэмдэгт байх тэмдэгт байхгүй бол бид хоёрдахь тэмдэгтийг эхний тэмдэгтийг сольж өгөх боломжтой. Үгүй бол мөр нь изоморф биш юм.

Алгоритм

  1. Эхлүүлэх a тэмдэгт to тэмдэгт hashmap солих болон тэмдэгт to boolean hashmap ашигласан
  2. Мөр доторх тэмдэгт бүрийн хувьд давтах s болон t:
    • If солих агуулсан s [i] түлхүүр болгон:
      • If орлуулах [s [i]]! = t [i]
        • хуурамчаар буцаах
    • Бусад:
      • If ашигласан [t [i]] == үнэн
        • хуурамчаар буцаах
      • багц орлуулах [s [i]] = t [i]
      • багц ашигласан [t [i]] = үнэн
  3. Буцах үнэн

Изоморф утаснуудын Leetcode шийдлийг хэрэгжүүлэх

C ++ програм

#include <bits/stdc++.h>

using namespace std;

bool isIsomorphic(string s , string t) {
    int n = s.length();

    unordered_map <char , char> replacement;
    unordered_map <char , bool> used;

    for(int i = 0 ; i < n ; i++)
    {
        if(replacement.count(s[i]))
        {
            if(replacement[s[i]] != t[i])
                return false;
        }
        else
        {
            if(used[t[i]])
                return false;
            replacement[s[i]] = t[i];
            used[t[i]] = true;
        }
    }

    return true;
}

int main() {
    string s = "abb" , t = "cdd";
    cout << (isIsomorphic(s , t) ? "true" : "false") << endl;
    return 0;
}

Java програм

import java.util.*;

class isomorphic_string {
    public static void main(String args[]) {
        String s = "abb" , t = "cdd";
        System.out.println(isIsomorphic(s , t) ? "true" : "false");
    }

    public static boolean isIsomorphic(String s , String t) {
        HashMap <Character , Character> replacement = new HashMap <>();
        HashMap <Character , Boolean> used = new HashMap <>();

        for(int i = 0 ; i < s.length() ; i++) {
            if(replacement.containsKey(s.charAt(i))) {
                if(replacement.get(s.charAt(i)) != t.charAt(i))
                    return false;
            }
            else {
                if(used.containsKey(t.charAt(i)))
                    return false;
                replacement.put(s.charAt(i) , t.charAt(i));
                used.put(t.charAt(i) , true);
            }
        }

        return true;
    }
}
true

Изоморфын мөрүүдийг Leetcode шийдлийн нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N), N = s ба t мөрийн урт.

Сансрын нарийн төвөгтэй байдал 

O (1), оролтод тогтмол тооны өвөрмөц тэмдэгтүүд байх тул.