My 16ms C++ solution


  • 0
    Q
    class Solution {
    	bool **map;
    	int m, n;
    	bool exi(vector<vector<char>>& board, string word, bool **map, int x, int y) {
    		if (board[x][y] == word[0]) {
    			if (word.length() <= 1) return true;
    			map[x][y] = true;
    			if (x + 1 < m && map[x + 1][y] == false) {
    				if (exi(board, word.substr(1, word.length() - 1), map, x + 1, y)) return true;
    			}
    			if (x > 0 && map[x - 1][y] == false) {
    				if (exi(board, word.substr(1, word.length() - 1), map, x - 1, y)) return true;
    			}
    			if (y + 1 < n && map[x][y + 1] == false) {
    				if (exi(board, word.substr(1, word.length() - 1), map, x, y + 1)) return true;
    			}
    			if (y > 0 && map[x][y - 1] == false) {
    				if (exi(board, word.substr(1, word.length() - 1), map, x, y - 1)) return true;
    			}
    		}
    		map[x][y] = false;
    		return false;
    	}
    public:
    	bool exist(vector<vector<char>>& board, string word) {
    	    if (board.size() == 0 || board[0].size() == 0) return false;
    		n = board[0].size(), m = board.size();
    		map = (bool**)malloc(m * sizeof(bool*));
    		for (int i = 0; i < m; ++i) {
    			map[i] = (bool*)malloc(n * sizeof(bool));
    			memset(map[i], false, n * sizeof(bool));
    		}
    		for (int i = 0; i < m; ++i)
    		for (int j = 0; j < n; ++j) {
    			if (exi(board, word, map, i, j)) {
    			        for (int i = 0; i < m; ++i) free(map[i]);
    		                free(map);
    		                return true;
    			}
    		}
    		for (int i = 0; i < m; ++i) free(map[i]);
    		free(map);
    		return false;
    	}
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.