Medium

题目描述

给你一个 m x n 的矩阵 board，它代表一个纵横填字游戏的当前状态。纵横填字游戏格式为：空格用 ' ' 表示，阻挡格子用 '#' 表示，已经填入的字母用小写英文字母表示。

如果单词可以 水平放置（从左到右 或 从右到左）或 垂直放置（从上到下 或 从下到上），那么该单词就可以放在字谜中，需要满足：

  • 该单词不占用任何 '#' 对应的格子。
  • 每个字母对应的格子要么是 ' '（空格）要么与放置的字母相同。
  • 如果单词是水平放置的，那么该单词左、右两侧相邻格子不能是 ' ' 或小写英文字母。
  • 如果单词是垂直放置的，那么该单词上、下两侧相邻格子不能是 ' ' 或小写英文字母。

给定一个字符串 word ，如果 word 能够被放在 board 中，则返回 true ，否则返回 false 。

示例 1：

输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc"
输出：true
解释：单词 "abc" 可以如上图放置（从上到下）。

示例 2：

输入：board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac"
输出：false
解释：无法放置该单词，因为放置该单词后，其上方或下方相邻的格子有空格。

示例 3：

输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", " ", "c"]], word = "ca"
输出：true
解释：单词 "ca" 可以如上图放置（从右到左）。

提示：

  • m == board.length
  • n == board[i].length
  • 1 <= m * n <= 2 * 10^5
  • board[i][j] 只会是 ' '、'#' 或小写英文字母
  • 1 <= word.length <= max(m, n)
  • word 只包含小写英文字母

解题思路

这道题需要检查一个单词是否可以放置在纵横填字游戏板中。关键是理解放置规则和边界条件。

解题思路：

  1. 四个方向枚举：单词可以水平（左到右、右到左）或垂直（上到下、下到上）放置，共4个方向。

  2. 起始位置判断：对于每个可能的起始位置，需要检查：

    • 单词能否完整放置（不越界且不碰到 #）
    • 每个位置要么是空格 ' ' 要么与单词对应字母相同
    • 边界条件：单词两端不能有空格或字母相邻

  3. 边界检查：这是关键部分，需要确保：

    • 单词起始位置的前一个位置（如果存在）不能是空格或字母
    • 单词结束位置的后一个位置（如果存在）不能是空格或字母

  4. 优化策略：

    • 只从可能的起始位置开始检查（边界或 # 后面的位置）
    • 对于每个方向，遍历所有可能的起始点
    • 使用辅助函数检查单词是否可以从某个位置按某个方向放置

算法步骤：

  1. 定义四个方向的增量：右、左、下、上
  2. 对于每个方向，遍历所有可能的起始位置
  3. 对于每个起始位置，检查是否可以放置完整单词
  4. 检查边界条件确保单词两端正确隔离

代码实现

class Solution {
public:
    bool placeWordInCrossword(vector<vector<char>>& board, string word) {
        int m = board.size(), n = board[0].size();
        int len = word.length();
        
        // 四个方向：右、左、下、上
        vector<pair<int, int>> dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        for (auto& dir : dirs) {
            int dx = dir.first, dy = dir.second;
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (canPlace(board, word, i, j, dx, dy)) {
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
    
private:
    bool canPlace(vector<vector<char>>& board, string& word, int startX, int startY, int dx, int dy) {
        int m = board.size(), n = board[0].size();
        int len = word.length();
        
        // 检查前一个位置（如果存在）是否为空格或字母
        int prevX = startX - dx, prevY = startY - dy;
        if (prevX >= 0 && prevX < m && prevY >= 0 && prevY < n) {
            if (board[prevX][prevY] != '#') return false;
        }
        
        // 检查是否能放置完整单词
        for (int k = 0; k < len; k++) {
            int x = startX + k * dx;
            int y = startY + k * dy;
            
            // 越界检查
            if (x < 0 || x >= m || y < 0 || y >= n) return false;
            
            // 被阻挡或字母不匹配
            if (board[x][y] == '#') return false;
            if (board[x][y] != ' ' && board[x][y] != word[k]) return false;
        }
        
        // 检查后一个位置（如果存在）是否为空格或字母
        int nextX = startX + len * dx, nextY = startY + len * dy;
        if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) {
            if (board[nextX][nextY] != '#') return false;
        }
        
        return true;
    }
};

class Solution:
    def placeWordInCrossword(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        word_len = len(word)
        
        # 四个方向：右、左、下、上
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        def can_place(start_x, start_y, dx, dy):
            # 检查前一个位置
            prev_x, prev_y = start_x - dx, start_y - dy
            if 0 <= prev_x < m and 0 <= prev_y < n:
                if board[prev_x][prev_y] != '#':
                    return False
            
            # 检查是否能放置完整单词
            for k in range(word_len):
                x, y = start_x + k * dx, start_y + k * dy
                
                # 越界检查
                if not (0 <= x < m and 0 <= y < n):
                    return False
                
                # 被阻挡或字母不匹配
                if board[x][y] == '#':
                    return False
                if board[x][y] != ' ' and board[x][y] != word[k]:
                    return False
            
            # 检查后一个位置
            next_x, next_y = start_x + word_len * dx, start_y + word_len * dy
            if 0 <= next_x < m and 0 <= next_y < n:
                if board[next_x][next_y] != '#':
                    return False
            
            return True
        
        for dx, dy in directions:
            for i in range(m):
                for j in range(n):
                    if can_place(i, j, dx, dy):
                        return True
        
        return False

public class Solution {
    public bool PlaceWordInCrossword(char[][] board, string word) {
        int m = board.Length, n = board[0].Length;
        int len = word.Length;
        
        // 四个方向：右、左、下、上
        int[,] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        
        for (int d = 0; d < 4; d++) {
            int dx = dirs[d, 0], dy = dirs[d, 1];
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (CanPlace(board, word, i, j, dx, dy)) {
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
    
    private bool CanPlace(char[][] board, string word, int startX, int startY, int dx, int dy) {
        int m = board.Length, n = board[0].Length;
        int len = word.Length;
        
        // 检查前一个位置
        int prevX = startX - dx, prevY = startY - dy;
        if (prevX >= 0 && prevX < m && prevY >= 0 && prevY < n) {
            if (board[prevX][prevY] != '#') return false;
        }
        
        // 检查是否能放置完整单词
        for (int k = 0; k < len; k++) {
            int x = startX + k * dx;
            int y = startY + k * dy;
            
            // 越界检查
            if (x < 0 || x >= m || y < 0 || y >= n) return false;
            
            // 被阻挡或字母不匹配
            if (board[x][y] == '#') return false;
            if (board[x][y] != ' ' && board[x][y] != word[k]) return false;
        }
        
        // 检查后一个位置
        int nextX = startX + len * dx, nextY = startY + len * dy;
        if (nextX >= 0 && nextX < m && nextY >= 0 && nextY < n) {
            if (board[nextX][nextY] != '#') return false;
        }
        
        return true;
    }
}

var placeWordInCrossword = function(board, word) {
    const m = board.length;
    const n = board[0].length;
    
    function canPlace(row, col, dr, dc, word) {
        // Check if there's a blocked cell before the word
        const prevRow = row - dr;
        const prevCol = col - dc;
        if (prevRow >= 0 && prevRow < m && prevCol >= 0 && prevCol < n && 
            board[prevRow][prevCol] !== '#') {
            return false;
        }
        
        // Check each character of the word
        for (let i = 0; i < word.length; i++) {
            const r = row + i * dr;
            const c = col + i * dc;
            
            // Out of bounds
            if (r < 0 || r >= m || c < 0 || c >= n) {
                return false;
            }
            
            // Blocked cell
            if (board[r][c] === '#') {
                return false;
            }
            
            // Cell must be empty or match the character
            if (board[r][c] !== ' ' && board[r][c] !== word[i]) {
                return false;
            }
        }
        
        // Check if there's a blocked cell after the word
        const nextRow = row + word.length * dr;
        const nextCol = col + word.length * dc;
        if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && 
            board[nextRow][nextCol] !== '#') {
            return false;
        }
        
        return true;
    }
    
    // Try all positions and directions
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            // Horizontal left to right
            if (canPlace(i, j, 0, 1, word)) return true;
            // Horizontal right to left
            if (canPlace(i, j, 0, -1, word)) return true;
            // Vertical top to bottom
            if (canPlace(i, j, 1, 0, word)) return true;
            // Vertical bottom to top
            if (canPlace(i, j, -1, 0, word)) return true;
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(m×n×L)
空间复杂度O(1)

其中 m 和 n 分别是 board 的行数和列数，L 是 word 的长度。时间复杂度中，我们需要遍历所有可能的起始位置(m×n)，对于每个位置需要检查4个方向，每个方向最多检查L个字符。空间复杂度为常数，只使用了几个变量。