制作一个在唯一时自动检测的功能

Question

我需要一个 C++ 函数，只要输入是唯一的，就从字符串向量中获取一个元素。

例如，我的矢量包含{"DELETE", "HELP", "GO FORWARD", "GO BACKWARDS"}。

如果我的输入是 "H"，函数应该输出 "HELP" 如果输入是 "H 55"，它应该忽略 55 并且仍然输出 "HELP"。

但是，当我向矢量添加新元素 "HELLO" 时，它应该 return "NOT UNIQUE".

我已经尝试了很多东西，但我并没有真正取得任何进展。

我认为二维向量是一个可能的解决方案，但我无法让它工作：

["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

一种可能的方法如下所示：

#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;
}

程序输出可见here.

Answer 2

对于（自定义）Trie，您可能会执行以下操作：

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

制作一个在唯一时自动检测的功能

Make a function that autodetects when unique

c++

algorithm

qt

vector

2d-vector