Reverse Words in a String
لديك سلسلة نصية s تتكوّن من كلمات ومسافات. الكلمة هي سلسلة متتابعة من الأحرف والأرقام لا تحتوي على مسافة بداخلها. يمكن أن تفصل بين الكلمات أكثر من مسافة واحدة، ويمكن أن تبدأ s بمسافات أو تنتهي بها.
أعِد الكلمات بترتيب عكسي، مع فصلها بمسافة واحدة بالضبط، ومن دون مسافة في البداية أو النهاية. تحتفظ كل كلمة بتهجئتها؛ الذي يتغيّر هو ترتيب الكلمات فقط.
الدالة
- sstring
- أحرف وأرقام ومسافات تحتوي على كلمة واحدة على الأقل
- تُرجعstring
- كلمات s بترتيب عكسي، مفصولة بمسافات مفردة
القيود
1 ≤ s.length ≤ 104sيحتوي فقط على أحرف إنجليزية وأرقام ومسافات.sيحتوي على كلمة واحدة على الأقل.
أمثلة
- المدخلات
- s = "Coddy runs in 15 languages"
- المخرجات
- "languages 15 in runs Coddy"
- الشرح
- الكلمات هي
Coddyوrunsوinو15وlanguages. عند قراءتها من الأخيرة إلى الأولى، تعطيlanguages 15 in runs Coddy؛ وتُعدّ15كلمةً لأن الكلمات قد تحتوي على أرقام.
- المدخلات
- s = " practice makes progress "
- المخرجات
- "progress makes practice"
- الشرح
- تُحذف المسافات عند الطرفين، وتُختزل مجموعتا المسافتين والثلاث مسافات بين الكلمات إلى مسافة واحدة. وتظهر الكلمات الثلاث بترتيب عكسي، من الأخيرة إلى الأولى:
progress makes practice.
- المدخلات
- s = " single "
- المخرجات
- "single"
- الشرح
- تُقرأ قائمة مكوّنة من كلمة واحدة بالطريقة نفسها عند عكسها. تختفي المسافات المحيطة بها فقط، لذا فالإجابة هي
single.
سؤال إضافي
هل يمكنك عكس ترتيب الكلمات مع الحفاظ على المسافات في s: مجموعات المسافات نفسها، وبالأطوال نفسها، وبالترتيب نفسه؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
تجاهل المسافات للحظة. إذا كانت الكلمات لديك بالفعل في قائمة، فكيف ستبني الإجابة؟ ثم اسأل نفسك كيف تؤثر المسافات الإضافية في الخطوة التي تقسّم السلسلة إلى كلمات.
قسِّم عند المسافات واحذف الأجزاء الفارغة التي تخلّفها مسافتان متتاليتان، أو مسافة في أيٍّ من الطرفين. اعكس ترتيب قائمة الكلمات ثم صِلْ بينها بمسافات مفردة.
للعمل داخل مصفوفة أحرف واحدة بدلًا من ذلك: اعكس المصفوفة بأكملها، ما يضع الكلمات بالترتيب الصحيح لكنه يجعل تهجئة كل كلمة معكوسة. ثم اعكس كل كلمة مجددًا، وانسخ أحرفها إلى الأمام باستخدام فهرس ثانٍ، بحيث تتقلص كل مجموعة متتالية من المسافات إلى مسافة واحدة.
الحل
ترتيب الكلمات هو عكس واحد؛ أما المسافات فهي موضع تعثّر الحلول. يجب حذف المسافات في الطرفين والمسافات المتكررة بين الكلمات، مع وضع مسافة واحدة بالضبط بين الكلمات في الإجابة. يمكنك تقسيم النص إلى قائمة من الكلمات، أو عكس السلسلة بأكملها ثم عكس كل كلمة داخل مصفوفة واحدة.
قسّم إلى كلمات ثم صِلها بترتيب عكسي
الفكرة
قسّم s إلى كلماتها، واعكس القائمة، ثم ادمجها باستخدام مسافات مفردة. يتطلب التقسيم عناية: فتقسيم " practice makes progress " عند كل مسافة مفردة يعطي ستة أجزاء فارغة حول الكلمات الثلاث. احذف الأجزاء الفارغة، فتصبح القائمة practice، makes، progress.
تقرأ عملية التقسيم كل محرف مرة واحدة، وتكتب عملية الدمج كل محرف مُحتفَظ به مرة واحدة، لذا فالزمن هو O(n) لسلسلة طولها n. وتتطلب قائمة الكلمات والإجابة مساحة إضافية قدرها O(n).
الخوارزمية
- قسّم
sعند المسافات. - احذف الأجزاء الفارغة.
- اعكس قائمة الكلمات.
- اربط الكلمات مع وضع مسافة واحدة بين كل كلمتين، ثم أعد النتيجة.
def reverseWords(s):
# split() with no argument treats any run of spaces as one separator
# and ignores spaces at both ends.
words = s.split()
words.reverse()
return " ".join(words)اعكس السلسلة بأكملها، ثم اعكس كل كلمة
الفكرة
يضع عكس السلسلة النصية كاملةً الكلمات بالترتيب الصحيح، لكنه يكتب كل كلمة معكوسة: تصبح Coddy runs in 15 languages segaugnal 51 ni snur yddoC. ثم يؤدي عكس كل كلمة على حدة إلى languages 15 in runs Coddy.
تُعالَج المسافات في المرور نفسه. يتحرك الفهرس read عبر المصفوفة المعكوسة ويتجاوز المسافات؛ ويحدد الفهرس write الموضع الذي يوضع فيه الحرف التالي الذي سنحتفظ به. لا تؤدي عملية النسخ مطلقًا إلى الكتابة فوق حرف ما زلت بحاجة إليه، لأن write لا يتجاوز read: فالمسافة الواحدة المكتوبة قبل الكلمة تحل محل مسافة واحدة على الأقل تجاوزها read.
يُنسخ كل حرف مرة واحدة على الأكثر ويُبادَل مرتين على الأكثر، لذا يكون الزمن O(n)، مع مساحة إضافية O(1) في مخزن أحرف يمكنك تعديله. تصل السلاسل النصية هنا على هيئة قيم، لذا تُنشئ كل حل نسخة عمل واحدة من s: وتكون الذاكرة الإجمالية O(n).
الخوارزمية
- انسخ
sإلى مصفوفة أحرف واعكس المصفوفة بأكملها. - تصفّح المصفوفة باستخدام مؤشر قراءة وتخطَّ المسافات.
- عند كل كلمة، اكتب مسافة واحدة أولًا ما لم تكن الكلمة الأولى، ثم انسخ أحرف الكلمة إلى مؤشر الكتابة.
- اعكس الجزء الذي نسخته لكي تُقرأ الكلمة من اليسار إلى اليمين.
- أعِد أول
writeحرفًا.
def reverseWords(s):
chars = list(s)
def reverse(lo, hi):
while lo < hi:
chars[lo], chars[hi] = chars[hi], chars[lo]
lo += 1
hi -= 1
n = len(chars)
reverse(0, n - 1) # words in the right order, each spelled backwards
write = 0
read = 0
while read < n:
if chars[read] == " ":
read += 1
continue
if write > 0:
chars[write] = " " # one space before every word but the first
write += 1
start = write
while read < n and chars[read] != " ":
chars[write] = chars[read]
write += 1
read += 1
reverse(start, write - 1) # spell the word forwards again
return "".join(chars[:write])
أخطاء شائعة وحالات حدّية
- التقسيم عند مسافة واحدة والاحتفاظ بكل جزء. يؤدي تقسيم
"a b"إلىaوجزء فارغ وb، وتعيد عملية الربط مسافتين:"b a". - الاعتماد على أن التقسيم سيحذف الأجزاء الفارغة من الطرفين. تحذف
split(" ")في Java الأجزاء الفارغة في النهاية، لكنها تحتفظ بها في البداية، لذا تظل هناك واحدة في" a b". - إضافة مسافة بعد كل كلمة، بما فيها الأخيرة، بحيث تنتهي الإجابة بمسافة. ضع المسافة قبل كل كلمة ما عدا الأولى.
- إجراء عملية عكس واحدة فقط في النسخة التي تعمل في المكان نفسه. يؤدي عكس الكلمات وحدها إلى
yddoC snur ni 51 segaugnal. - في PHP وR، قد يصل الإدخال المكوّن من أرقام فقط، مثل
2026، على هيئة عدد. حوّله إلى سلسلة نصية قبل تقسيمه.
أسئلة شائعة3
ما هو التعقيد الزمني لعكس الكلمات في سلسلة نصية؟
تعمل كلتا الطريقتين في زمن O(n) لسلسلة طولها n، لأن كل محرف يُقرأ ويُكتب عددًا ثابتًا من المرات. يتطلب التقسيم مساحة إضافية O(n) لقائمة الكلمات. أما عكس السلسلة بأكملها ثم عكس كل كلمة فيتطلب مساحة إضافية O(1) على مصفوفة محارف يمكنك تعديلها.
كيف تتعامل مع المسافات المتعددة بين الكلمات؟
اعتبر الكلمة سلسلةً من الأحرف غير الفارغة، ولا تنسخ أبدًا المسافات من الإدخال. التقسيم من دون فاصل في Python وRuby، وstrings.Fields في Go وsplit_whitespace في Rust، تتجاهل بالفعل كل سلسلة من المسافات والمسافات في كلا الطرفين؛ وفي الأماكن الأخرى، احذف الأجزاء الفارغة. ثم اكتب مسافة واحدة بين الكلمات.
هل يمكنك عكس ترتيب الكلمات دون استخدام دالة تقسيم؟
نعم. امسح من الطرف الأيمن: تخطَّ المسافات، وحدد مكان انتهاء الكلمة، وتحرك يسارًا إلى بدايتها، وأضف الكلمة مع مسافة قبلها ما لم تكن الأولى. تُزار كل محرف مرة واحدة، لذا يظل الزمن O(n)، وتظهر الكلمات بترتيب عكسي من دون الحاجة إلى قائمة لعكسها.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def reverseWords(s):
# اكتب الشيفرة هنااختبار #1
اختبار #2
اختبار #3
وسيط
s = "Coddy runs in 15 languages"
الإخراج المتوقع
"languages 15 in runs Coddy"