Cari anagram dan sabanagram dalam semua kata dalam bahasa tersebut

Memecahkan masalah dengan anagram memunculkan ide:
Berapa banyak kata yang tersisa jika Anda menghapus semua anagram dan sangangram dari kamus bahasa Rusia

Kamus yang ditemukan mengandung lebih dari 1,5 juta kata dalam berbagai bentuk.

Anda dapat membandingkan setiap kata dengan masing-masing, tetapi untuk 1,5 juta entri panjang dan tidak optimal.
Di dunia dengan memori tak terbatas, Anda dapat membuat substring dari semua permutasi dari setiap kata dan memeriksa kamus kami pada mereka.

Tetapi apakah ada solusi yang lebih baik?

Mari kita mulai dengan terminologi:

Anagram - kata yang diperoleh dengan menata ulang huruf
Contoh: roket dan kereta

Sabanagram - kata yang dapat terdiri dari huruf kata lain
Contoh: lengkung - sabanagram kata roket

Tugas :

Katakanlah kamus kami terdiri dari lima kata rumit:

roket , kereta , lengkungan , cat , dahak

Menambahkan kamus ke pohon awalan (Trie)
Setiap simpul pohon berisi pasangan: huruf + nomornya dalam kata
Node diurutkan secara alfabet dan dengan frekuensi huruf dalam kata



Algoritma (dalam bentuk yang disederhanakan):

Ambil lantai, nr. cat:

Kami mencari simpul yang dimulai dengan huruf minimum dari kata (โ€œkโ€)

(Dalam gambar, simpul tersebut ditandai dengan warna ungu)

Segera setelah kami menemukan simpul seperti itu, kami mencari di subtree untuk lintasan yang berisi huruf yang tersisa dalam jumlah yang tepat.

Dalam kata dahak di bawah simpul K-1 ada O-2 dan T-1, yang cukup untuk kata kucing

kami.Keuntungan dari struktur data seperti itu adalah kita dapat dengan cepat keluar dari subtree jika huruf simpul> dari huruf yang kita

lihat. Setelah memeriksa kamus kami, kami menemukan bahwa hanya dahak yang bukan anagram atau sabanagram kata lain

Kode Java
 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;
    }



โ†’ Versi lengkap kode dengan dua kamus dan tes

PS

Untuk kamus Rusia dari 1,5 juta, 242399 kata tersisa dalam 13 menit
Untuk kamus bahasa Inggris dari 416 ribu tersisa 49251 dalam 45 detik

Anda dapat mengoptimalkan kamus asli dengan menghapus kata saat ini dari itu jika yang berikutnya mulai dengan itu

All Articles