Reverse a String

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

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

Q: كيف تعكس سلسلة نصية دون استخدام دالة عكس مضمّنة؟

انسخ الأحرف إلى مصفوفة، وضع مؤشرًا عند كل طرف، وبدّل الحرفين، ثم حرّك المؤشرين نحو بعضهما حتى يلتقيا. وبدلًا من ذلك، كرّر من الفهرس الأخير نزولًا إلى الأول، وألحِق كل حرف بمنشئ السلسلة. تنتج كلتا الطريقتين السلسلة المعكوسة في تمريرة واحدة.

Q: هل يمكنك عكس سلسلة نصية في مكانها؟

فقط عندما تكون الأحرف موجودة في مخزن مؤقت قابل للتغيير، مثل مصفوفة char في C أو Java أو C#، أو قائمة في Python، أو std::string في C++. تكون السلاسل النصية في Java وPython وJavaScript والعديد من اللغات الأخرى غير قابلة للتغيير، لذا تنسخها إلى مصفوفة، وتبدّل الأحرف داخلها، ثم تنشئ سلسلة نصية جديدة. وتتم خطوة التبديل نفسها في المكان في كلتا الحالتين.

Q: لماذا تتوقف حلقة المؤشرين عند المنتصف؟

يضع كل تبديل حرفين في موضعيهما النهائيين، لذا بعد n / 2 تبديلات يكون كل حرف في موضعه الصحيح. الاستمرار بعد المنتصف يبدّل الأزواج نفسها مرة أخرى، فيلغي ما تم إنجازه. عندما يكون الطول فرديًا، يكون الحرف الأوسط في فهرس صورته المعكوسة أصلًا، ولا يحتاج إلى تبديل.

مبتدئالمصفوفات والسلاسل النصية مؤشران

+10

لديك سلسلة نصية s مكوّنة من أحرف إنجليزية وأرقام. أعد سلسلة نصية جديدة تحتوي على الأحرف نفسها بترتيب معكوس، بحيث يأتي الحرف الأخير أولًا والأول أخيرًا. أبقِ كل حرف كما هو تمامًا، بما في ذلك حالة الأحرف.

الدالة

reverseString(s: string) → string

sstring: السلسلة المراد عكسها
تُرجعstring: أحرف s بترتيب عكسي

القيود

1 ≤ s.length ≤ 10⁴
s لا يحتوي إلا على أحرف إنجليزية (a إلى z، وA إلى Z) وأرقام (0 إلى 9).

أمثلة

المدخلات: s = "Coddy2026"
المخرجات: "6202yddoC"
الشرح: اقرأ Coddy2026 من آخر حرف فيه إلى أوله: 6، 2، 0، 2، ثم y، d، d، o وأخيرًا الحرف الكبير C.

المدخلات: s = "noon"
المخرجات: "noon"
الشرح: كلمة noon متناظرة، لذا فإن عكسها هو الكلمة نفسها. يتبادل الحرفان n في الطرفين موضعيهما، ثم يفعل الحرفان o ذلك.

+14 اختبارات مخفية عند الإرسال

سؤال إضافي

كيف يمكنك عكس ترتيب الكلمات في جملة، وتحويل hello big world إلى world big hello، مع الحفاظ على ترتيب حروف كل كلمة؟

تلميحات

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

فُتح 0 من 3

الحل

لكل حرف موضع ثابت: الحرف عند الفهرس i ينتمي إلى الفهرس n-1-i. يمكنك كتابة الأحرف في سلسلة جديدة بهذا الترتيب، أو تبديلها على شكل أزواج بدءًا من الطرفين. التبديل هو الطريقة التي يطلبها المحاورون في المقابلات، لأن تحريك المؤشرين نفسيهما يعكس مصفوفة في مكانها ويتحقق مما إذا كانت متناظرة.

انسخ الأحرف من الخلف

الفكرة

يبدأ معكوس s بآخر محرف من s، ثم يتابع بالمحرف ما قبل الأخير، وينتهي بالمحرف الأول. لذا مرّر فهرسًا من n-1 نزولًا إلى 0، وأضف كل محرف إلى الإجابة عند الوصول إليه. بالنسبة إلى Coddy2026، تضيف 6، و2، و0، و2، وy، وهكذا، لتكوين 6202yddoC.

تُقرأ كل محرف مرة واحدة وتُكتب مرة واحدة، لذا يكون العمل O(n). الإجابة عبارة عن سلسلة ثانية تتكوّن من n محرفًا، وهذا يتطلب مساحة إضافية O(n).

طريقة الإضافة مهمة. فإضافة محرف واحد إلى سلسلة غير قابلة للتغيير باستخدام + تنسخ السلسلة بأكملها في كل مرة، وبالنسبة إلى n = 10^4 فهذا يعني نحو 5 × 10^7 عملية نسخ للمحارف. اجمع المحارف في قائمة أو في أداة إنشاء السلاسل، ثم ادمجها مرة واحدة في النهاية.

الخوارزمية

أنشئ قائمة فارغة أو أداةً لبناء سلسلة نصية للإجابة.
كرّر i من n-1 تنازليًا حتى 0.
أضف s[i] إلى الإجابة.
ادمج عناصر الإجابة في سلسلة نصية وأعِدها.

def reverseString(s):
    result = []
    for i in range(len(s) - 1, -1, -1):
        result.append(s[i])
    return "".join(result)

بدّل من الطرفين باستخدام مؤشرين

الفكرة

يعكس الترتيب أزواج الأحرف بدءًا من الخارج إلى الداخل. يتبادل الحرف الأول والأخير موضعيهما، ثم الثاني وما قبل الأخير، وهكذا باتجاه الوسط. ضع مؤشرًا left عند الفهرس 0 ومؤشرًا right عند الفهرس n-1، وبدّل الحرفين، ثم حرّك كلا المؤشرين خطوة واحدة نحو الداخل.

توقّف عندما يلتقي المؤشران أو يتجاوز أحدهما الآخر. في noon يبدأ المؤشران عند 0 و3، ثم ينتقلان إلى 1 و2، وبعد ذلك يتجاوز أحدهما الآخر، وذلك بعد تبديلين. في سلسلة ذات طول فردي مثل xYz، يلتقيان عند الحرف الأوسط، الذي يكون في موضعه النهائي بالفعل، لذا لا يتم لمسه مطلقًا. يضع كل تبديل حرفين في موضعيهما النهائيين، لذا تكفي n / 2 من التبديلات لإنجاز المهمة.

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

الخوارزمية

انسخ s إلى مصفوفة من الأحرف.
عيّن left = 0 وright = n-1.
ما دام left < right، بدّل الحرفين عند left وright، ثم أضف 1 إلى left واطرح 1 من right.
حوّل المصفوفة مرة أخرى إلى سلسلة وأعِدها.

def reverseString(s):
    chars = list(s)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return "".join(chars)

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

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

تكرار الحلقة باستخدام left حتى n-1. بعد الوصول إلى المنتصف، يُبدَّل كل زوج مرة ثانية، فيعود النص كما كان. توقّف عند left < right.
بدء الحلقة العكسية من n بدلًا من n-1، ما يؤدي إلى قراءة موضع واحد بعد النهاية. أمّا في Lua وR، فتبدأ الفهارس من 1 وتنتهي عند n.
بناء الإجابة باستخدام result = result + ch مع سلسلة نصية غير قابلة للتغيير. تنسخ كل خطوة كل ما بُني حتى تلك اللحظة، ما يحوّل مهمة خطية إلى مهمة تربيعية مع المدخلات الطويلة.
نسيان '\0' المنهي في C. فالمخزن المؤقت الذي يتسع لـ n بايتات ينقصه بايت واحد؛ خصّص n + 1.
التبديل دون استخدام متغير مؤقت: بعد chars[left] = chars[right] يضيع الحرف القديم الموجود في الموضع الأيسر، إلا إذا كانت لغتك تبدّل القيمتين معًا.

أسئلة شائعة4

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

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

كيف تعكس سلسلة نصية دون استخدام دالة عكس مضمّنة؟

انسخ الأحرف إلى مصفوفة، وضع مؤشرًا عند كل طرف، وبدّل الحرفين، ثم حرّك المؤشرين نحو بعضهما حتى يلتقيا. وبدلًا من ذلك، كرّر من الفهرس الأخير نزولًا إلى الأول، وألحِق كل حرف بمنشئ السلسلة. تنتج كلتا الطريقتين السلسلة المعكوسة في تمريرة واحدة.

هل يمكنك عكس سلسلة نصية في مكانها؟

فقط عندما تكون الأحرف موجودة في مخزن مؤقت قابل للتغيير، مثل مصفوفة char في C أو Java أو C#، أو قائمة في Python، أو std::string في C++. تكون السلاسل النصية في Java وPython وJavaScript والعديد من اللغات الأخرى غير قابلة للتغيير، لذا تنسخها إلى مصفوفة، وتبدّل الأحرف داخلها، ثم تنشئ سلسلة نصية جديدة. وتتم خطوة التبديل نفسها في المكان في كلتا الحالتين.

لماذا تتوقف حلقة المؤشرين عند المنتصف؟

يضع كل تبديل حرفين في موضعيهما النهائيين، لذا بعد n / 2 تبديلات يكون كل حرف في موضعه الصحيح. الاستمرار بعد المنتصف يبدّل الأزواج نفسها مرة أخرى، فيلغي ما تم إنجازه. عندما يكون الطول فرديًا، يكون الحرف الأوسط في فهرس صورته المعكوسة أصلًا، ولا يحتاج إلى تبديل.

Python

def reverseString(s):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

s = "Coddy2026"

المتوقع

"6202yddoC"