时间戳

首页 > 解决方案 > 使用similarity() 函数查找相似的字符串

c++ - 使用similarity() 函数查找相似的字符串

问题描述

假设一个函数similarity()接受两个字符串作为参数。如果两个字符串相似，则返回接近 1 的数字，否则返回接近 0 的数字。

到目前为止，我有一个二叉树，其中每个节点都包含一个字符串作为数据。我想创建一个函数，它将逐个节点浏览该树节点并返回具有最高相似性的单词。

试图：

使用@AshutoshRaghuwanshi 的答案，我得到了

void Tree::traverse(Node* rootNode, float& score, std::string& bestMatch, std::string& word)
{
    if(rootNode == nullptr) return;
    if(similarity(rootNode->data, word)>score){
        score = similarity(rootNode->data, word);
        bestMatch = rootNode->data;
    }
    traverse(rootNode->left, score, bestMatch, word);
    traverse(rootNode->right, score, bestMatch, word);
}

std::string Tree::browseTree(const std::string& word) const{
    if(isEmpty()){
        throw std::invalid_argument("The tree is empty!");
    }

    Node * currentNode = root;
    float score=0;
    std::string bestMatch;

    traverse(currentNode->left, score, bestMatch, word);
    traverse(currentNode->right, score, bestMatch, word);

    if(score>.90){
        return bestMatch;
    }else{
        throw std::invalid_argument("Word not found");
    }
}

好像没那么好用？我哪里错了？

标签： c++recursionbinary-treetraversal

解决方案

void Tree::traverse(Node* rootNode, float& score, std::string& bestMatch, std::string& word)
{
    if(rootNode == nullptr) return;
    float s = similarity(rootNode->data, word);
    if(s>score){
        score = s;
        bestMatch = rootNode->data;
    }   
    traverse(rootNode->left, score, bestMatch, word);
    traverse(rootNode->right, score, bestMatch, word);
}

std::string Tree::browseTree(const std::string& word) const{
    if(isEmpty()){
        throw std::invalid_argument("The tree is empty!");
    }

    Node * currentNode = root; //replace this line
    float score=0;
    std::string bestMatch;

    traverse(root, score, bestMatch, word);

    if(score>.90){
        return bestMatch;
    }else{
        throw std::invalid_argument("Word not found");
    }
}

这段代码很可能会起作用。请将注释中指示的行替换为二叉树的实际根节点。

推荐阅读