文章目录
1. 题目
2. 解题
1. 题目
给你一个 m x n 的矩阵 board ，它代表一个填字游戏 当前 的状态。
填字游戏格子中包含小写英文字母（已填入的单词），表示 空格 的 ' ' 和表示 障碍 格子的 '#' 。
如果满足以下条件，那么我们可以 水平 （从左到右 或者 从右到左）或 竖直 （从上到下 或者 从下到上）填入一个单词：
该单词不占据任何 '#' 对应的格子。
每个字母对应的格子要么是 ' ' （空格）要么与 board 中已有字母 匹配 。
如果单词是 水平 放置的，那么该单词左边和右边 相邻 格子不能为 ’ ’ 或小写英文字母。
如果单词是 竖直 放置的，那么该单词上边和下边 相邻 格子不能为 ’ ’ 或小写英文字母。
给你一个字符串 word ，如果 word 可以被放入 board 中，请你返回 true ，否则请返回 false 。
输入：board = [["#", " ", "#"], [" ", " ", "#"], ["#", "c", " "]], word = "abc" 输出：true 解释：单词 "abc" 可以如上图放置（从上往下）。
输入：board = [[" ", "#", "a"], [" ", "#", "c"], [" ", "#", "a"]], word = "ac" 输出：false 解释：无法放置单词，因为放置该单词后上方或者下方相邻格会有空格。
输入：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 只包含小写英文字母。
2. 解题
- 按题意模拟
class Solution { int m, n; public: bool placeWordInCrossword(vector<vector<char>>& board, string word) { m = board.size(), n = board[0].size(); for(int i = 0; i < m; ++i) if(check(board, i, word, 0)) return true; for(int j = 0; j < n; ++j) if(check(board, j, word, 1)) return true; return false; } bool check(vector<vector<char>>& b, int idx, string word, int flag) { unordered_map<int,char> cp;//记录board位置上的字符映射关系 if(flag == 0) { int j = 0, len = 0;//len记录board有效的字符长度 while(j < n) { if(b[idx][j] == '#' || j == n-1) { // 遇到结束符号 if(isalpha(b[idx][j])) { cp[len] = b[idx][j]; } if(b[idx][j] != '#') len++; if(check(cp, len, word)) return true; cp.clear(); len = 0; } else if(b[idx][j] == ' ') len++; else{ cp[len] = b[idx][j]; len++; } j++; } } else { int i = 0, len = 0; while(i < m) { if(b[i][idx] == '#' || i == m-1) { if(isalpha(b[i][idx])) { cp[len] = b[i][idx]; } if(b[i][idx] != '#') len++; if(check(cp, len, word)) return true; cp.clear(); len = 0; } else if(b[i][idx] == ' ') len++; else{ cp[len] = b[i][idx]; len++; } i++; } } return false; } bool check(unordered_map<int,char> &cp, int len, string& word) { if(len != word.size()) return false;//长度不等，不能 if(cp.size() == 0) return true; bool flag1 = true, flag2 = true;//正反顺序都可以进行检查 for(auto& x : cp) { if(word[x.first] != x.second)//正序 { flag1 = false; break; } } if(flag1) return true; for(auto& x : cp) { if(word[len-1-x.first] != x.second) // 逆序检查 { flag2 = false; break; } } return flag2; } };
336 ms 414.9 MB C++
