หาแถวซ้ำในเมทริกซ์ไบนารีด้วย Trie ใน C++

โจทย์

ให้เมทริกซ์ไบนารี (มีค่า 0 และ 1) ต้องการหาแถวที่ซ้ำกัน ตัวอย่างเมทริกซ์ 6x6 มีแถวซ้ำที่ตำแหน่ง 3, 4, 5 (นับจาก 0)

วิธีแก้ปัญหา

ใช้โครงสร้างข้อมูล Trie (Prefix Tree) ซึ่งเหมาะสำหรับเก็บและค้นหาข้อมูลที่ชุดตัวอักษรน้อย (0, 1) ความซับซ้อนในการค้นหาเทียบเท่าความยาวของคีย์

ขั้นตอน:

1. สร้าง Trie สำหรับเก็บแถวของเมทริกซ์
2. แทรกแถวทีละแถวเข้า Trie
3. ถ้าแถวที่เพิ่งแทรกมีอยู่แล้ว → แถวนั้นซ้ำ

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

const int MAX = 100;

class Trie {
public:
    bool leaf_node;
    Trie* children[2];
};

Trie* getNode() {
    Trie* node = new Trie;
    node->children[0] = node->children[1] = NULL;
    node->leaf_node = false;
    return node;
}

bool insert(Trie*& head, bool* arr, int N) {
    Trie* curr = head;
    for (int i = 0; i < N; i++) {
        if (curr->children[arr[i]] == NULL)
            curr->children[arr[i]] = getNode();
        curr = curr->children[arr[i]];
    }
    if (curr->leaf_node) return false;
    return (curr->leaf_node = true);
}

void displayDuplicateRows(bool matrix[][MAX], int M, int N) {
    Trie* head = getNode();
    for (int i = 0; i < M; i++)
        if (!insert(head, matrix[i], N))
            cout << "There is a duplicate row at position: " << i << endl;
}

int main() {
    bool mat[][MAX] = {
        {1, 1, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {1, 0, 1, 1, 0, 0},
        {1, 1, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {0, 0, 1, 0, 0, 1},
    };
    displayDuplicateRows(mat, 6, 6);
}

ผลลัพธ์

There is a duplicate row at position: 3
There is a duplicate row at position: 4
There is a duplicate row at position: 5