c++ - 在自定义类 vector 中查找

Question

我正在练习这段代码(来自 LeetCode)，以便在 C++ 中做得更好。不幸的是，我无法让“查找”正常工作。
此代码用于从 char 类型 vector (即 board)的 vector 中搜索 word，而无需访问同一个字母两次(visitedSoFar 保留一个字母 visitedSoFar 的 x,y 位置的轨迹)。
Node 类的 vector 用于存储到目前为止访问过的位置。
这是我编写的代码片段:

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

如果我对查找进行评论，我会得到正确的输出，但这不适用于所有测试用例。

谢谢。

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

编辑
该词可以由顺序相邻单元格的字母构成，其中“相邻”单元格是水平或垂直相邻的单元格。同一字母单元格不得使用多次。

编辑
设计错误:find操作应该是找不到(说明该节点目前还没有被访问过)然后在里面进行搜索。因此将 find 更改为 == visitedSoFar.end() 而不是 != visitedSoFar.end()。

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

这可以隐藏实现从判断一个单词是否包含在面板中的界面中进行搜索。