بكفاءة عكس ترتيب الكلمات في مصفوفة أحرف

يعتبر عكس ترتيب الكلمات في مصفوفة أحرف مشكلة كلاسيكية تختبر فهمك للخوارزميات ومعالجة السلاسل. سواء كنت تستعد لمقابلة عمل أو كنت تتطلع فقط لتطوير مهاراتك في البرمجة، فإن إتقان هذه التحديات يعد مكافئًا جدًا. في هذا المقال، سنستكشف المشكلة بالتفصيل ونحلل حلاً فعالًا بلغة C/C++.

المشكلة

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

"هذا نص"

يجب أن تكون النتيجة:

"نص هذا"

تحدد التحدي أن هذه العملية يجب أن تتم في زمن O(N) ومساحة O(1)، مما يعني أنك لا تستطيع استخدام دوال مثل split() أو أي هياكل بيانات مثل المكدسات التي تتلاعب بمساحة إضافية.

تحليل المشكلة

تعقيد الزمن

يتطلب تعقيد الزمن O(N) أن تقوم الخوارزمية بتمرير خطي عبر البيانات. لذا يجب علينا تجنب الحلقات المتداخلة التي تزيد من تعقيد الزمن.

تعقيد المكان

بالنسبة لتعقيد المكان O(1)، لا يمكننا استخدام أي هياكل بيانات إضافية للتخزين. هذا يعني أن العمليات يجب أن تتم مباشرة داخل مصفوفة الإدخال.

الحل

دعنا نقوم بتفصيل الحل خطوة بخطوة. سنستخدم نهج ذي مرورين لحل هذه المشكلة بكفاءة.

الخطوة 1: عكس السلسلة بالكامل

الخطوة الأولى هي عكس المصفوفة بالكامل. هذا يحول السلسلة الأصلية إلى سلسلة حيث يتم عكس جميع الأحرف. بالنسبة لمثالنا "هذا نص" بعد العكس:

"صن اذه"

الخطوة 2: عكس كل كلمة

الآن بعد أن عكسنا السلسلة بالكامل، نحتاج إلى عكس كل كلمة فردية لإعادتها إلى الترتيب الصحيح. إليك كيفية تنفيذ هذه الخطوات في C/C++:

void swap(char* str, int i, int j) {
    char t = str[i];
    str[i] = str[j];
    str[j] = t;
}

void reverse_string(char* str, int length) {
    for(int i = 0; i < length / 2; i++) {
        swap(str, i, length - i - 1);
    }
}

void reverse_words(char* str) {
    int l = strlen(str);
    // عكس السلسلة بالكامل
    reverse_string(str, strlen(str));
    int p = 0;
 
    // العثور على حدود الكلمات وعكس كل كلمة
    for(int i = 0; i < l; i++) {
        if(str[i] == ' ') {
            reverse_string(&str[p], i - p);  // عكس الكلمة المحددة
            p = i + 1;
        }
    }
    // أخيرًا عكس الكلمة الأخيرة.
    reverse_string(&str[p], l - p);
}

شرح الكود

1. دالة التبديل: نستخدم دالة مساعد swap لتبديل الأحرف في المصفوفة.
2. دالة عكس السلسلة: هذه الدالة تعكس أحرف السلسلة باستخدام دالة التبديل.
3. دالة عكس الكلمات: الدالة الأساسية تعكس أولاً مصفوفة الأحرف بالكامل ثم تتكرر عبرها لعكس الكلمات الفردية المحددة بواسطة المسافات. يتم التعامل مع الكلمة الأخيرة بعد انتهاء الحلقة.

تحليل التعقيد

يعني العكس عبر المصفوفة مرتين أن تعقيد الزمن هو O(N):

• المرور الأول: O(N) لعكس السلسلة بالكامل.
• المرور الثاني: O(N) لعكس كل كلمة.

لذا، يبقى تعقيد الزمن النهائي O(N). أما تعقيد المساحة فهو O(1) حيث لا تُستخدم أي مساحة إضافية باستثناء المتغيرات للدوران.

الخاتمة

يتطلب عكس ترتيب الكلمات في مصفوفة أحرف بكفاءة مزيجًا من معالجة السلاسل وفهم الوصول إلى الفهارس. تُظهر الخوارزمية المقدمة هنا نهجًا واضحًا يلبي متطلبات O(N) زمنًا وO(1) مكانًا أثناء استخدام C/C++. تدرب على هذا الحل، وستجد أنه إضافة ممتازة لمجموعة أدوات البرمجة الخاصة بك!