C++ Online Compiler
Example: Print Unique Rows using Trie in C++
C
C++
C#
Java
Python
PHP
main.cpp
STDIN
Run
// Print Unique Rows using Trie #include <iostream> #include <vector> #include <memory> // For std::unique_ptr using namespace std; // Trie Node structure struct TrieNode { unique_ptr<TrieNode> children[2]; // children[0] for '0', children[1] for '1' bool isEndOfRow; // Marks if a path ending at this node represents a complete row TrieNode() : isEndOfRow(false) { children[0] = nullptr; children[1] = nullptr; } }; // Function to insert a row into the Trie and check for uniqueness // Returns true if the row was unique (i.e., newly inserted), false otherwise bool insert(TrieNode* root, const vector<int>& row) { TrieNode* curr = root; bool isNewRow = false; // Flag to check if we created any new nodes for (int bit : row) { if (curr->children[bit] == nullptr) { curr->children[bit] = make_unique<TrieNode>(); isNewRow = true; // A new path segment was created } curr = curr->children[bit].get(); } // If isNewRow is true, it means we created at least one new node, // making the entire path (row) unique until this point. // Also, if the current node's isEndOfRow was false, but now we mark it true, // that also signifies a unique *complete* row. if (!curr->isEndOfRow) { curr->isEndOfRow = true; isNewRow = true; // This specific row is now marked as complete for the first time } return isNewRow; } // Function to print unique rows using Trie void printUniqueRowsTrie(const vector<vector<int>>& matrix) { int R = matrix.size(); if (R == 0) return; // Handle empty matrix // No need for C, as vector<int> row can handle different lengths (though typical for matrices to be uniform) // Create the root of the Trie TrieNode* root = new TrieNode(); // Using raw pointer for root, manage memory with smart pointers for children for (const auto& row : matrix) { // If insert returns true, it means this row was unique if (insert(root, row)) { for (int bit : row) { cout << bit << " "; } cout << endl; } } // Clean up dynamically allocated root node // For simplicity in this example, manual delete for root. // In a full application, a smart pointer or a wrapper class for Trie would handle this. delete root; } int main() { // Step 1: Define the boolean matrix vector<vector<int>> matrix = { {0, 1, 0, 0}, {1, 0, 1, 1}, {0, 1, 0, 0}, {1, 1, 0, 0} }; cout << "Unique rows in the matrix (using Trie):" << endl; // Step 2: Call the function to print unique rows using Trie printUniqueRowsTrie(matrix); // Another example matrix cout << "\nUnique rows for another matrix (using Trie):" << endl; vector<vector<int>> matrix2 = { {1, 1}, {0, 1}, {1, 1}, {0, 0}, {1, 0} }; printUniqueRowsTrie(matrix2); return 0; }
Output
Clear
ADVERTISEMENTS