【LeetCode】 79. Word Search

Description

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Constraints:

• board and word consists only of lowercase and uppercase English letters.
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

給予一個二維的面板和一個單字，找到單字是否存在於網格中。

單字可以被鄰近格子裡的字母所組成，鄰近的格子定義為水平或垂直的鄰居。同樣格子中的字母不能被使用兩次，

限制：

• board 和 word 只會包含大小寫英文字母。
• 1 <= board.length <= 200
• 1 <= board[i].length <= 200
• 1 <= word.length <= 10^3

Example:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "ABCCED", return true.
Given word = "SEE", return true.
Given word = "ABCB", return false.

Solution

• 使用DFS去跑網格。
• 每次跑格子時，如果是符合的字就移除單字第一個字和格子中的字，接著檢查鄰居；不同就回傳false。
• 需要特別注意，測資可能故意設計的很大，要盡量避免耗時的動作。
  • 如vector的操作等等。
  • 其實我下面code的substr應該也挺浪費時間的，可以試著改寫。

Code

class Solution {
public:
    bool DFS(vector<vector<char>>& board, string word, int x, int y)
    {
        if(word.empty()) return true;
        if(x < 0 || y < 0 || x >= board[0].size() || y >= board.size())
            return false;
        if(board[y][x] != word.front())
            return false;
        else
        {
            char save = board[y][x];
            board[y][x] = 0;
            bool temp = DFS(board, word.substr(1), x + 1, y) ||
                DFS(board, word.substr(1), x - 1, y)||
                DFS(board, word.substr(1), x, y + 1)||
                DFS(board, word.substr(1), x, y - 1);
            board[y][x] = save;
            return temp;
        }
    }
    bool exist(vector<vector<char>>& board, string word) {
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board[0].size(); j++)
                if(DFS(board, word, j, i))
                    return true;
        return false;
    }
};

tags: LeetCode C++