79. 单词搜索-极致优化，可行性剪枝和顺序剪枝

        给你一个目标字符串，和一个二维字符数组，判断在数组中是否能找到目标字符串。

        例如，board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

算法思路

1. 以每个单元格作为搜索起点，使用深度优先搜索（DFS）寻找可能匹配目标单词的路径

2. DFS实现要点：

   • 终止条件：当匹配位置pos达到目标单词长度时，说明找到完整路径
   • 搜索过程：从当前位置向四个方向扩展，检查边界条件并进行回溯
   • 防重处理：在递归入口检查是否已访问，并验证当前字符是否匹配目标单词首字母

3. 优化策略：

   • 可行性剪枝：若目标单词中某字符出现频率超过board中的总数，直接终止
   • 顺序优化：当目标单词尾字符出现频率低于首字符时，翻转单词可减少无效分支

     class Solution {
     public:
         static constexpr int dx[4] = {0,0,-1,1},dy[4] = {-1,1,0,0};
         bool dfs(int x,int y,int pos,string &word,int m,int n,vector<vector<char>>& board,vector<vector<int>>& vis) {
             if (pos == word.size()) {
                 return true;
             }
             for (int i = 0;i < 4;i++) {
                 int bx = dx[i] + x,by = dy[i] + y;
                 if (bx < 0 || bx >= m || by < 0 || by >= n || board[bx][by] != word[pos] || vis[bx][by]) {
                     continue;
                 } 
                 vis[bx][by] = 1;
                 if(dfs(bx,by,pos + 1,word,m,n,board,vis)) return true;
                 vis[bx][by] = 0;
             }
             return false; 
         }
         bool exist(vector<vector<char>>& board, string word) {
             int m = board.size(),n = board[0].size();
             vector<vector<int>> vis(m,vector<int> (n,0));
             unordered_map<char,int> bd_cnt;
             for (auto &row : board) {
                 for (auto &p : row) {
                     bd_cnt[p]++;
                 }
             }
             unordered_map<char,int> word_cnt;
             if (word_cnt[word.back()] < word_cnt[word[0]]) {
                 ranges::reverse(word);
             }
             for (auto &w : word) {
                 if(++word_cnt[w] > bd_cnt[w]) return false;
             }
             for (int i = 0;i < m;i++) {
                 for (int j = 0;j < n;j++) {
                     if (board[i][j] == word[0]) {
                         vis[i][j] = 1;
                         if (dfs(i,j,1,word,m,n,board,vis)) {
                             return true;
                         }else{
                             vis[i][j] = 0;
                         }
                     }
                 }
             }
             return false;
         }
     };

                时间复杂度：O(mn3^4)，m和n为行列数，对于每个入口最多有三个分支(因为上一个点已经搜索了一个方向)，所以为O(mn3^4)

                空间复杂度：O(1)