Isomorphic ညှို့ Leetcode ဖြေရှင်းချက်


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Adobe က အမေဇုံ Apple ဘလွန်းဘာ့ဂ် Facebook က Google Intel က LinkedIn တို့ Microsoft က Oracle က Yahoo က
HashMap ကြိုး

ပြProbleနာဖော်ပြချက်

ဒီပြproblemနာမှာကျွန်တော်တို့ကိုနှစ်ခုပေးထားတယ် ညှို့, a နှင့် b ။ ကျွန်ုပ်တို့၏ရည်မှန်းချက်မှာကြိုးနှစ်ချောင်းသည် isomorphic ဟုတ်မဟုတ်သိရန်ဖြစ်သည်။

Strings နှစ်ခုကို isomorphic လို့ခေါ်ပါတယ်။ ပထမ string မှာပါတဲ့အက္ခရာများကိုဇာတ်ကောင်များ၏ဆက်စပ်မှုကိုအတူတူပင်ထားရှိပြီးဖြစ်ပေါ်လာသည့်နေရာအားလုံးတွင် (သူ့ဟာသူအပါအ ၀ င်) မည်သည့်ဇာတ်ကောင်ကိုမဆိုအစားထိုးနိုင်မှသာလျှင်ဟုခေါ်သည်။ အဘယ်သူမျှဇာတ်ကောင်နှစ် ဦး တည်းအတူတူဇာတ်ကောင်မှ map နိုင်ပါတယ်။

နမူနာ

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

Isomorphic ညှို့ Leetcode ဖြေရှင်းချက်

ချဉ်းကပ်နည်း

ပထမဆုံး string ရှိ character တိုင်းအတွက်အစားထိုးသိမ်းဆည်းရန် hashmaps ကိုသုံးနိုင်သည်။ အကယ်၍ ကျွန်ုပ်တို့သည်ပထမဆုံးဇာတ်ကောင်ကိုအစားထိုးရန်နေရာတစ်ခုသို့ရောက်လျှင်၊

  • အစားထိုးသည်အခြား string တစ်ခုရှိအက္ခရာနှင့်တူညီမှုရှိမရှိစစ်ဆေးနိုင်သည်။ မရရှိလျှင်, string ကို isomorphic မဖြစ်နိုင်ပါ။
  • ပထမဇာတ်ကောင်အတွက်အစားထိုးခြင်းမရှိပါက၊ ဒုတိယစာလုံး၏ပထမစာကြောင်းတွင်အခြားအက္ခရာများအတွက်အစားထိုးအဖြစ်ဒုတိယအက္ခရာကိုအသုံးပြုမသုံးစစ်ဆေးနိုင်သည်။ ဤစစ်ဆေးမှုသည်အရေးကြီးသည်၊ အဘယ်ကြောင့်ဆိုသော်ကျွန်ုပ်တို့သည်ပထမ ဦး ဆုံး string တွင်ရှိသောဇာတ်ကောင်တိုင်းကိုထူးခြားသော character တစ်ခုသို့ map ရန်လိုအပ်သောကြောင့်ဖြစ်သည်။ ဒုတိယအက္ခရာဖြစ်သောအစားထိုးဇာတ်ကောင်မရှိပါကဒုတိယအက္ခရာကိုအစားထိုးရန်ဒုတိယအက္ခရာကိုသတ်မှတ်နိုင်သည်။ ဒီလိုမှမဟုတ်ရင်ညှို့ isomorphic မရှိကြပေ။

algorithm

  1. ကန ဦး စတင်သည် ဇာတ်ကောင် သို့ ဇာတ်ကောင် hashmap အစားထိုး နှင့်တစ်ဦး ဇာတ်ကောင် သို့ ရေနံချောင်း hashmap အသုံးပြုခံ့
  2. string ထဲရှိဇာတ်ကောင်တိုင်းအတွက် Iterate s နှင့် t:
    • If အစားထိုး ပါဝင်ပါသည် s [i] သော့တစ်ခုအဖြစ်:
      • If အစားထိုး [s [i]]! = t ကို [ဈ]
        • return false
    • ကျန် -
      • If စစ်မှန်တဲ့ = t ကို [t [ဈ]] ကိုအသုံးပြုခဲ့သည်
        • return false
      • အစုံ အစားထိုး [s [i]] = t [i]
      • အစုံ စစ်မှန်တဲ့ = [t [ဈ]] ကိုအသုံးပြုခဲ့သည်
  3. ပြန်လာမှန်

Isomorphic ညှို့ 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

Isomorphic ညှို့ Leetcode ဖြေရှင်းချက်၏ရှုပ်ထွေးအားသုံးသပ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ = ညှို့ s နဲ့ t ရဲ့အရှည်။

အာကာသရှုပ်ထွေးမှု 

အို (၁)၊ input ကိုအတွက်ထူးခြားတဲ့ဇာတ်ကောင်တစ် ဦး စဉ်ဆက်မပြတ်အရေအတွက်ကရှိလိမ့်မည်အဖြစ်။