在自定义类向量中查找

Question

我正在练习这段代码（来自LeetCode），以便更好地掌握C ++。不幸的是，我无法正确使用“find”。此代码用于在类型为char的vector的vector（即board）中搜索word，而不访问相同的字母（visitedSoFar跟踪已访问字母的x，y位置）。一个存储到目前为止访问位置的Node类向量被用来存储位置。
这是我编写的代码片段：

class Node{
    private:
        int x;
        int y;

    public:
        Node(int a, int b):x(a),y(b){};
        bool operator==(Node newNode){
            if(this->x == newNode.x && this->y == newNode.y)
                return true;
            else 
                return false;
        }
};

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        vector <Node> visitedSoFar;

        for(int r =0; r< board.size(); r++){
            for(int c=0; c<board[r].size(); c++){
                if(board[r][c] == word.at(0)){

                if(search(board, word, visitedSoFar, board[r].size(), r, c))
                    return true;
                }
            }
        }
        return false;
    }

    private:
    bool search(vector<vector<char>>& board, string word, vector<Node>& visitedSoFar, int size, int r, int c){
        Node newNode(r,c);
        visitedSoFar.push_back(newNode);

        if(word.size() == 1)
            return true;

        Node toSearch1(r-1,c);
        if(r-1 >= 0 && find(visitedSoFar.begin(), visitedSoFar.end(), toSearch1) == visitedSoFar.end()){
            if(board[r-1][c] == word.at(1))
                if(search(board, word.substr(1), visitedSoFar, size, r-1, c))
                    return true;
        }

        Node toSearch2(r+1,c);
        if(r+1 < size && find(visitedSoFar.begin(), visitedSoFar.end(), toSearch2) == visitedSoFar.end()){
            if(board[r+1][c] == word.at(1))
                if(search(board, word.substr(1), visitedSoFar, size, r+1, c))
                    return true;
        }

        Node toSearch3(r,c-1);
        if(c-1 >= 0 && find(visitedSoFar.begin(), visitedSoFar.end(), toSearch3) == visitedSoFar.end()){
            if(board[r][c-1] == word.at(1))
                if(search(board, word.substr(1), visitedSoFar, size, r, c-1))
                    return true;
        }

        Node toSearch4(r,c+1);
        if(c+1 < size && find(visitedSoFar.begin(), visitedSoFar.end(), toSearch4) == visitedSoFar.end()){
            if(board[r][c+1] == word.at(1))
                if(search(board, word.substr(1), visitedSoFar, size, r, c+1))
                    return true;
        }
        visitedSoFar.pop_back();
        return false;
    }
};

如果我注释掉find，我会得到正确的输出，但这对于所有测试用例都不起作用。

谢谢。

编辑 在search方法中，修正了if语句以检查(r+1)和(c+1)的大小。

编辑 单词可以由相邻单元格的字母构成，其中“相邻”单元格是水平或垂直相邻的单元格。不能重复使用同一字母单元格。

编辑 设计错误：find操作不应该能够找到（表明节点到目前为止还没有被访问），然后在其中进行搜索。因此，将find更改为== visitedSoFar.end()而不是!= visitedSoFar.end()。

- Prameet Singh Kohli

---

你没有给我们提供 main 程序，也没有测试数据或期望输出。-- 我正在练习这段来自 LeetCode 的代码，以更好地掌握 C++ -- 而要 “更好地掌握 C++”，就需要学习如何使用调试器，获得调试技能，而不仅仅是编写程序，希望它能正常运行，如果不能正常工作，就去 SO 上寻求帮助。 - PaulMcKenzie

建议：Solution 类没有太多意义，它不存储状态。它的方法看起来几乎像 C 代码。我会将 class 更改为 namespace，或者将 board 和 visitedSoFar 设为类成员。 - xinaiz

您确定要检查 c+1 和 r+1 >=0 吗？难道不应该与棋盘的维度进行比较吗？例如 c+1 < n r+1 < n 等等。另外，在 Node 类的 operator== 中，请传递引用类型的 Node。 - Ravi

@PaulMcKenzie 我来自C语言的背景，因此我的编程风格类似于C。 - Prameet Singh Kohli

@PrameetSinghKohli -- 我从未提到过C编程，但更重要的是，你仍然没有提供一个完整的[mcve]，强调完整。 - PaulMcKenzie

@PaulMcKenzie： 由于我是在一个网站上练习这个，他们没有提供主函数。我正在构建一个主函数，将编辑代码以包含它。谢谢。 - Prameet Singh Kohli

Answer 1

我认为你应该使用更简单的解决方案设计。

检查每个棋盘点背后的想法很可能是不必要的工作，对吧？使用你的方法，你不断地检查工作是否已经完成。这种检查包括在每次搜索步骤中通过你的棋盘进行线性搜索（每个节点都将在某个时候保存）。这意味着你可以避免大部分检查，因为要做的工作几乎相同。

因此，一个快速编码的解决方案就像这样。

bool row_contains_word(vector<char> const& row, string word)
{
  if(word.size() > row.size())
    throw std::invalid_argument("Word is longer then the row!!");

  // linear search for the word in board
  for(int i = 0; i < row.size() - word.size(); ++i) // start point
  {
    // check realtive to the start point if its the word there
    for(int j = 0; j < word.size(); ++j) 
    {
      if(row[i+j] != word[j])
        break; // we can continue to check the next position
      // last position we check here, and match means its the word
      else if(j == (word.size() - 1) && row[i+j] == word[j])
        return true;
    }
  }
  return false;

使用这个函数（我认为这不是一个真正好的实现方式，但只是为了举例）你可以简单地循环：

for(int r = 0; r < board.size(); ++r)
{
  if(row_contains_word(board[r], word))
     return true;
}
// and same with colums as well

正如评论中所提到的，Solution不是类的候选对象。 它可以这样写：

namespace Solution
{
  bool search(vector<vector<char>> const& board, string word); // implementaion follows

  namespace // anonymous namespace, not accessible from the outside world, but only this compilation unit(.cpp file)
  {
    bool row_contains_word(vector<char> const& row, string word);
    bool col_contains_word(/*vector<char> const& row,*/ string word); // this needs more work, since the col is a little different
  }
}

这可以将实现从决定单词是否包含在板子中的接口搜索中隐藏起来。

- jonas_toth

---

感谢Black Moses和@jonas_toth指导我使用命名空间来维护代码，而不是使用“class solution”。这确实是正确的方法。 然而，由于我正在使用一个网站来练习编写C++代码，我对已经给我提供的模板没有太多发言权。 现在，我正在集中精力检查find函数是否被正确实现，或者我是否遗漏了什么？ - Prameet Singh Kohli