Make a function that autodetects when unique

Question

I need to have a function in c++ that gets an element from a vector of strings as soon as the input is unique.

For example, my vector contains {"DELETE", "HELP", "GO FORWARD", "GO BACKWARDS"}.

If my input is then "H", the function should output "HELP" If the input is "H 55", it should ignore the 55 and still output "HELP".

However, when I add a new element "HELLO" to my vector, it should return "NOT UNIQUE".

I already tried a bunch of things, but I am not really getting anywhere.

I think a 2 dimensional vector would be a possible solution, but I have not been able to make it work:

["DELETE", "D"]
["DELETE", "DE"]
["DELETE", "DEL"]
["DELETE", "DELE"]
["DELETE", "DELET"]
["DELETE", "DELETE"]
["HELP", "HELP"]
["HELLO", "HELL"]
["HELLO", "HELLO"]
...

Answer 1

Make a function that autodetects when unique

One possible way of doing this is as shown below:

#include <iostream>
#include <vector>
#include <string>
std::string checkUnique(const std::string& searchString, const std::vector<std::string>& inputVector)
{
    int count = 0;
    std::string foundString;
    for(const std::string &element: inputVector)
    {
        if(element.at(0) == searchString.at(0))
        {
            foundString = element;
            ++count; //increment count
        }
    }
    if(count == 0)
    {
        return "NOT FOUND";
    }
    else if(count == 1)
    {
        return foundString;
    }
    else 
    {
        return "NOT UNIQUE";
    }
}
int main()
{
  
    std::vector<std::string> inputVector{"DELETE", "HELP", "GO FORWARD", "GO BACKWARDS"};
    
    std::string searchString = "H";
    
    //call the function for different cases 
    
    std::cout << checkUnique(searchString, inputVector) <<std::endl;;//prints HELP
    
    std::cout << checkUnique("H", inputVector) << std::endl;  //prints HELP
    
    std::cout << checkUnique("H 55", inputVector) << std::endl; //prints HELP 
    
    //add "HELLO" into the vector 
    inputVector.push_back("HELLO");
    
    std::cout << checkUnique("H", inputVector) << std::endl;  //prints NOT UNIQUE 

    std::cout << checkUnique("H 55", inputVector) << std::endl;  //prints NOT UNIQUE
    return 0;
}

The output of the program can be seen here.

Answer 2

With a (custom) Trie, you might do something like:

class Node
{
public:
    std::map<char, Node> children; // Might be a std::array<std::unique_ptr<Node>, 26>
    bool end_of_word = false;
    std::size_t count = 0; // number of words from that point

    Node() = default;

    const Node* get(char c) const
    {
        auto it = children.find(c);

        if (it == children.end()) {
            return nullptr;   
        }
        return &it->second;
    }
};

class Trie
{
    Node root;
public:
 
    void add(const std::string& word)
    {
        Node* node = &root;
        for (const char c : word) {
            node->count++;
            node = &node->children[c];
        }
        node->count++;
        node->end_of_word = true;
    }

    bool contains(const std::string& word) const
    {
        const Node* node = &root;
        for (const auto& c : word) {
            node = node->get(c);
            if (node == nullptr) {
                return false;
            }
        }
        return node->end_of_word;
    }
    
    std::optional<std::string> word_from_prefix(const std::string& s)
    {
        std::string res;
        const Node* node = &root;
        for (const auto& c : s) {
            auto next = node->get(c);
            if (next == nullptr) {
                break;
            }
            res += c;
            node = next;
        }
        if (node->count != 1) return std::nullopt;
        while (!node->end_of_word) {
            auto& [c, next] = *node->children.begin();
            res += c;
            node = &next;
        }
        return res;
    }
};

Demo