السلاسل المتشابهة حل Leetcode  


مستوى الصعوبة سهل
كثيرا ما يطلب في أدوبي أمازون أجهزة آبل بلومبرغ Facebook جوجل إنتل لينكد إن: Microsoft أوراكل ياهو
خوارزميات الترميز خريطة التجزئة المقابلة الشخصية مقابلة LeetCode LeetCodeSolutions خيط

المشكلة بيان  

في هذه المسألة ، لدينا اثنان سلاسل، أ و ب. هدفنا هو معرفة ما إذا كان الخيطان متماثلان أم لا.

تسمى سلسلتان متماثلان إذا وفقط إذا كان يمكن استبدال الأحرف الموجودة في السلسلة الأولى بأي حرف (بما في ذلك نفسه) في جميع نقاط حدوثها مع الحفاظ على الترتيب النسبي للأحرف كما هو. لا يمكن تعيين حرفين إلى نفس الشخصية.

مثال

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

السلاسل المتشابهة حل Leetcode

الرسالة  

يمكننا استخدام hashmaps لحفظ الاستبدال لكل حرف في السلسلة الأولى. إذا وصلنا إلى موضع يوجد فيه بديل للحرف الأول ،

  • يمكننا التحقق مما إذا كان الاستبدال هو نفس الحرف الموجود في السلسلة الأخرى. إذا لم يكن الأمر كذلك ، فلا يمكن أن تكون السلاسل متشابهة.
  • في حالة عدم وجود بديل للحرف الأول ، يمكننا التحقق مما إذا كان الحرف الثاني قد تم استخدامه كبديل لأي حرف آخر في السلسلة الأولى. هذا الفحص مهم لأننا نحتاج إلى تعيين كل حرف في السلسلة الأولى إلى حرف فريد. إذا لم يكن هناك حرف استبداله بالحرف الثاني ، فيمكننا تعيين الحرف الثاني كبديل للحرف الأول. خلاف ذلك ، فإن الأوتار ليست متشابهة.

خوارزمية

  1. تهيئة أ حرف إلى حرف خريطة التجزئة إستبدال و حرف إلى منطقية خريطة التجزئة مستعمل
  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;
}

برنامج جافا

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

تعقيد الوقت

يا (ن) ، ن = طول السلاسل s و t.

تعقيد الفضاء 

يا (1) ، حيث سيكون هناك عدد ثابت من الأحرف الفريدة في الإدخال.