ابحث عن الجناس الناقصة والصباحية في جميع كلمات اللغة

أدى حل المشكلات مع الجناس إلى الفكر:
كم عدد الكلمات المتبقية إذا قمت بإزالة جميع الجناس و sangangrams من قاموس اللغة الروسية

في القاموس يحتوي على أكثر من 1.5 مليون كلمة في أشكال مختلفة.

يمكنك مقارنة كل كلمة مع بعضها، ولكن ل1.5 مليون إدخالات أنها طويلة وليس الأمثل.
في عالم ذي ذاكرة لا نهائية ، يمكنك إنشاء سلاسل فرعية من جميع التباديل لكل كلمة والتحقق من قاموسنا عليها ،

ولكن هل هناك حل أفضل؟

دعونا نبدأ مع المصطلحات:

الجناس الناقص - كلمة التي حصلت عليها إعادة ترتيب الحروف
مثال: الصواريخ و النقل

Sabanagram - الكلمة التي يمكن أن تتكون من حروف كلمة أخرى
مثال: قوس - sabanagram كلمة الصواريخ

العمل :

ودعونا نقول يتكون قاموسنا من خمس كلمات صعبة:

صاروخ ، النقل ، قوس ، قطة ، بصاق

إضافة قاموس إلى شجرة البادئة (Trie)
تحتوي كل عقدة من الشجرة على زوج: حرف + رقمه في الكلمة
يتم ترتيب العقد أبجديًا وتردد الحرف في كلمة



الخوارزمية (في شكل مبسط):

خذ الكلمة n.r. cat:

نحن نبحث عن عقد تبدأ بالحرف الأدنى للكلمة ("k")

(في الشكل ، يتم تمييز هذه العقد باللون البنفسجي)

بمجرد العثور على هذه العقدة ، نبحث في الشجرة الفرعية للمسار الذي يحتوي على الأحرف المتبقية بالكمية المطلوبة

في كلمة البلغم أدناه العقدة K-1 هناك O-2 و T-1 ، وهو ما يكفي لكلمتنا cat.

ميزة بنية البيانات هذه هي أنه يمكننا الخروج بسرعة من الشجرة الفرعية إذا كان الحرف العقدي> من الحرف الذي

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

كود جافا
 public boolean isAnagramOrSubAnagram(Word word) {
        Character minCharacter = word.getMinCharacter();

        Stack<TrieNode> stack = new Stack<>();
        stack.add(root);

        while (!stack.isEmpty()) {
            TrieNode node = stack.pop();

            for (Entry<TrieKey, TrieNode> entry : node.getChildren().entrySet()) {
                char character = entry.getKey().getCharacter();
                if (character < minCharacter) {
                    stack.add(entry.getValue());
                } else if (character > minCharacter) {
                    break;
                } else if (entry.getKey().getCount() >= word.getCharacterCount(minCharacter)) {
                    if (doesMinWordCharacterNodeContainAnagram(entry, word)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }



النسخة الكاملة من الكود مع قواميس واختبارات

PS

لقاموس روسي من 1.5 مليون كلمة ، تبقى 242399 كلمة في 13 دقيقة
لقاموس إنجليزي من 416 ألف كلمة يسار 49251 في 45 ثانية

يمكنك تحسين القاموس الأصلي عن طريق إزالة الكلمة الحالية منه إذا بدأت الكلمة التالية به

All Articles