Isomorphic Strings

Q: ما هو التعقيد الزمني للسلاسل المتماثلة؟

يقرأ حلّ الخريطتين كل موضع مرة واحدة، لذا يعمل بزمن O(n) . وتحتوي الخريطتان على إدخال واحد كحد أقصى لكل محرف ممكن، أي 62 حرفًا ورقمًا، لذا تكون المساحة الإضافية O(1) . أما مقارنة كل زوج من المواضع فتستغرق O(n²) .

Q: لماذا تحتاج إلى خريطتي تجزئة للسلاسل المتشاكلة؟

تكتشف الخريطة من s إلى t حالة إعادة تسمية حرف واحد من s بطريقتين. لكنها لا تكشف حالة إعادة تسمية حرفين من s إلى الحرف نفسه، كما في ab و aa . وتكتشف الخريطة من t إلى s هذه الحالة.

سهلالتجزئة

+10

تكون سلسلتان متماثلتين شكليًا عندما يمكنك إعادة تسمية أحرف السلسلة الأولى للحصول على السلسلة الثانية. تحصل كل نسخة من الحرف على الاسم الجديد نفسه، ولا يحصل حرفان مختلفان على الاسم نفسه مطلقًا، ويمكن للحرف أن يحتفظ باسمه. لسلسلتين s وt لهما الطول نفسه، أعد true عندما تكونان متماثلتين شكليًا وfalse عندما لا تكونان كذلك.

الدالة

isIsomorphic(s: string, t: string) → boolean

sstring: السلسلة النصية المراد إعادة تسميتها، الحروف والأرقام
tstring: السلسلة المراد الوصول إليها، وبطول s نفسه
تُرجعboolean: صحيح إذا أمكن تحويل s إلى t عبر إعادة تسمية أحرفه تقابلًا واحدًا لواحد

القيود

1 ≤ s.length ≤ 2 × 10⁴
t.length == s.length
s وt يحتويان على أحرف إنجليزية وأرقام فقط. الأحرف الكبيرة والصغيرة محارف مختلفة.

أمثلة

المدخلات: s = "noon"t = "deed"
المخرجات: true
الشرح: أعِد تسمية n إلى d وo إلى e. يتوافق كل موضع مع إعادة التسمية هذه، ويحصل الحرفان على اسمين مختلفين.

المدخلات: s = "moon"t = "deed"
المخرجات: false
الشرح: من اليسار إلى اليمين، تصبح m هي d وتصبح o هي e، وبعد ذلك سيتعين أيضًا أن تصبح n هي d. لا يمكن لحرفين مختلفين أن يشتركا في الاسم نفسه، لذا فالإجابة هي false.

المدخلات: s = "r2d2"t = "c3p3"
المخرجات: true
الشرح: يصبح r c، ويصبح 2 3، ويصبح d p. الأرقام محارف أيضًا، ويصبح كلا 2 3.

سؤال إضافي

بالنظر إلى قائمة من الكلمات، هل يمكنك تجميع الكلمات المتشابهة بنيويًا معًا دون مقارنة كل زوج من الكلمات؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

يجب أن تعمل إعادة التسمية في كلا الاتجاهين: يتحول كل حرف في s إلى حرف واحد في t، ويأتي كل حرف في t من حرف واحد في s. تتحقق خريطتان، واحدة لكل اتجاه، من الأمرين في مرور واحد.

قارِن كل زوج من المواضع

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

تحافظ إعادة التسمية على تساوي الأحرف المتساوية واختلاف الأحرف المختلفة. لذا، لكل زوج من المواضع i وj، يجب أن تعطي s[i] == s[j] النتيجة نفسها التي تعطيها t[i] == t[j]. وهذا كافٍ أيضًا: إذا تطابقت النتيجة لكل زوج، فإن إعادة تسمية كل حرف في s إلى الحرف في t عند موضعه تكون محددة جيدًا، ولا تعطي حرفين اسمًا واحدًا أبدًا. في moon وdeed، يحتوي الموضعان 0 و3 على حرفين مختلفين في s، لكنهما يحتويان على الحرف d مرتين في t، لذا تكون النتيجة false.

يوجد نحو n²/2 زوجًا: أي 2 × 10^8 مقارنة عند n = 2 × 10^4 إذا لم يوقف أي زوج الحلقة مبكرًا.

الخوارزمية

كرّر المرور على كل فهرس i، ولكل واحد منها على كل فهرس لاحق j.
تحقّق مما إذا كانت s[i] تساوي s[j]، وما إذا كانت t[i] تساوي t[j].
إذا اختلفت الإجابتان، فأعِد false.
بعد آخر زوج، أعِد true.

def isIsomorphic(s, t):
    n = len(s)
    for i in range(n):
        for j in range(i + 1, n):
            # Two positions must hold equal characters in s exactly when they do in t
            if (s[i] == s[j]) != (t[i] == t[j]):
                return False
    return True

خريطتان، واحدة لكل اتجاه

الفكرة

أنشئ خريطة إعادة التسمية أثناء القراءة. تسجّل sToT ما أصبح عليه كل حرف من s، وتسجّل tToS من أين جاء كل حرف من t. عند الموضع i، حيث a = s[i] وb = t[i]، إما أن يكون كلاهما جديدًا فتصلهما، أو يجب أن يكونا مرتبطين أحدهما بالآخر مسبقًا.

خريطة واحدة لا تكفي. باستخدام sToT وحدها، تجتاز moon وdeed الاختبار، لأنه لا يُعاد تعيين أي حرف من s إلى حرفين مختلفين. لكن المشكلة هي أن m وn يتحولان كلاهما إلى d، وعند الموضع 3 تشير tToS بالفعل إلى أن d جاء من m.

يتطلب كل موضع بضع عمليات على الخرائط، لذا فالزمن هو O(n). رمز كل حرف أقل من 128، لذا يمكن أن تكون كل خريطة مصفوفة من 128 خانة: مساحة O(1). تنسخ نسختا R وSwift السلاسل أولًا إلى مصفوفات الرموز، وهذا يستغرق O(n).

الخوارزمية

أنشئ خريطتين فارغتين، sToT وtToS.
لكل فهرس i، ليكن a = s[i] وb = t[i].
إذا لم يكن a موجودًا في sToT ولم يكن b موجودًا في tToS، فاربط a بـ b وb بـ a.
وإلا، إذا كانت sToT[a] لا تساوي b أو كانت tToS[b] لا تساوي a، فأعِد false.
بعد الفهرس الأخير، أَعِد true.

def isIsomorphic(s, t):
    s_to_t = {}  # the character of t that each character of s became
    t_to_s = {}  # the character of s that each character of t came from
    for a, b in zip(s, t):
        if a not in s_to_t and b not in t_to_s:
            s_to_t[a] = b
            t_to_s[b] = a
        elif s_to_t.get(a) != b or t_to_s.get(b) != a:
            return False  # a already has another target, or b another source
    return True

أخطاء شائعة وحالات حدّية

الاحتفاظ بخريطة واحدة من s إلى t. فهي تقبل moon وdeed، وab وaa.
مقارنة عدد مرات ظهور كل حرف. يستخدم كلٌّ من abcabc وxyzxzy ثلاثة أحرف، مرتين لكلٍّ منها، ومع ذلك فإن حرف b الثاني يقابل z، بينما كان الأول يقابل y.
اعتبار حالة الأحرف متساوية. يحتوي aA على حرفين مختلفين، لذا لا يمكن أن يتحول إلى bb.
تحديد حجم خرائط المصفوفة بحيث تقتصر على الأحرف من a إلى z. فالأحرف الكبيرة والأرقام تقع خارج هذا النطاق؛ لذا استخدم رمز الحرف الكامل للفهرسة، مع 128 خانة.

أسئلة شائعة4

ما هو التعقيد الزمني للسلاسل المتماثلة؟

يقرأ حلّ الخريطتين كل موضع مرة واحدة، لذا يعمل بزمن O(n). وتحتوي الخريطتان على إدخال واحد كحد أقصى لكل محرف ممكن، أي 62 حرفًا ورقمًا، لذا تكون المساحة الإضافية O(1). أما مقارنة كل زوج من المواضع فتستغرق O(n²).

لماذا تحتاج إلى خريطتي تجزئة للسلاسل المتشاكلة؟

تكتشف الخريطة من s إلى t حالة إعادة تسمية حرف واحد من s بطريقتين. لكنها لا تكشف حالة إعادة تسمية حرفين من s إلى الحرف نفسه، كما في ab وaa. وتكتشف الخريطة من t إلى s هذه الحالة.

هل التماثل متماثل؟

نعم. يمكن التراجع عن إعادة التسمية واحدًا لواحد، لذا إذا أُعيدت تسمية s إلى t، فإن عكس كل اسم يعيد t إلى s. تتفق isIsomorphic(s, t) وisIsomorphic(t, s) دائمًا.

كيف يمكنك أيضًا التحقق مما إذا كانت سلسلتان متماثلتين؟

استبدل كل حرف بالموضع الذي يظهر فيه لأول مرة، ثم قارن النتائج. يتحول كل من noon وdeed إلى 0 1 1 0، بينما يتحول moon إلى 0 1 1 3. يستغرق ذلك أيضًا زمنًا قدره O(n)، مع ذاكرة قدرها O(n) للنمطين.

def isIsomorphic(s, t):
    # اكتب الكود هنا

اختبار #1

اختبار #2

اختبار #3

الوسائط

s = "noon"
t = "deed"

الإخراج المتوقع

true