Finden in Custom Class Vektor

Question

Ich übe diesen Code (von LeetCode), um in C++ besser zu sein. Leider kann ich nicht 'finden' richtig funktionieren.
Dieser Code Wort von einem Vektor des Vektor vom Typ char (d.h. Platte) ohne den Besuch die gleichen Buchstaben zweimal (visitedSoFar hält eine Spur des x, y-Positionen der Buchstaben visitedSoFar) zur Suche verwendet.
Ein Vektor der Klasse Knoten wird verwendet, um die bisher besuchten Positionen zu speichern.
Hier ist der Code-Schnipsel habe ich geschrieben:

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

Wenn ich den Fund Kommentar erhalte ich die richtige Ausgabe, aber dies für alle Testfälle nicht funktionieren würde.

Vielen Dank.

bearbeiten
In Methode Such berichtigte Anweisung Größe zu überprüfen für die (R + 1) und (c + 1).

bearbeiten
Das Wort kann aus Buchstaben von sequentiell benachbarten Zelle aufgebaut sein, wobei „benachbarte“ Zellen diejenigen horizontal oder vertikal benachbarten sind. Die gleiche Buchstabenzelle darf nicht mehr als einmal verwendet werden.

bearbeiten
Design-Fehler: Der Suchvorgang sollte nicht finden können sein (was anzeigt, dass der Knoten bisher nicht besucht wurde), um dann darin mit Suche fortzufahren. Daher wurde gefunden, dass es == visitedSoFar.end() und nicht! = VisitedSoFar.end() ist.

Answer 1

Ich denke, Sie sollten ein einfacheres Design Ihrer Lösung verwenden. Die Idee hinter jedem Boardpoint ist höchstwahrscheinlich unnötige Arbeit, oder? Mit Ihrem Ansatz überprüfen Sie ständig, ob die Arbeit bereits erledigt ist. Diese Überprüfung beinhaltet eine lineare Suche durch Ihr Board (jeder Knoten wird zu einem bestimmten Zeitpunkt gespeichert) für jeden Suchschritt. Dies bedeutet, dass Sie es sehr wahrscheinlich vermeiden können, es zu überprüfen, da die zu erledigende Arbeit fast die gleiche ist.

Dafür wäre eine schnell codierte Lösung wie folgt.

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; 

Mit dieser Funktion (ich glaube nicht, es ist ein wirklich guter Weg, es zu erreichen, aber nur ein Beispiel haben), können Sie einfach Schleife:

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

Wie in den Kommentaren erwähnt, Lösung ist nicht ein Kandidat für eine Klasse. Es könnte wie folgt geschrieben werden:

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

Dadurch wird die Implementierung von der Suche von der Schnittstelle zu entscheiden, verstecken kann, wenn ein Wort in der Platte enthalten ist.