79. Word Search

https://leetcode.com/problems/word-search/

Word Search - LeetCode

 

2차원 벡터에 문자의 목록과 단어가 주어졌을 때, 상하좌우로만 움직여서 해당 단어가 만들어지는지 확인하는 문제다.

보자마자 방법이 떠올라 만들었는데 자꾸 테스트케이스에 하나씩 하나씩 걸려서 개빡쳤다.

야근하고와서 시간도 없는데 쓸데없이 시간 잡아먹는거 같아 방법은 맞았으니 Discuss꺼 가져왔다.

 

시작점부터 상하좌우 반복해가면서 단어와 동일한지 체크하며 찾으면 되겠다.

---

class Solution { public:     bool exist(vector<vector<char> > &board, string word) {         m=board.size();         n=board[0].size();         for(int x=0;x<m;x++) {             for(int y=0;y<n;y++) {                 if(isFound(board,word.c_str(),x,y)) {                     return true;                 }             }         }         return false;     } private:     int m;     int n;     bool isFound(vector<vector<char> > &board, const char* w, int x, int y) {         if(x<0||y<0||x>=m||y>=n||board[x][y]=='\0'||*w!=board[x][y]) {             return false;         }         if(*(w+1)=='\0') {             return true;         }         char t=board[x][y];         board[x][y]='\0';         if( isFound(board,w+1,x-1,y)||isFound(board,w+1,x+1,y)||isFound(board,w+1,x,y-1)||isFound(board,w+1,x,y+1) ) {             return true;         }         board[x][y]=t;         return false;     } };

---