前言

中等 √ 繼續回溯，不知咋地感覺這兩題有點難度，是因為隔一天就手感生疏了嗎？

單詞搜索

我的題解

定義方向數組、二維訪問數組。圖搜索，向上下左右每個方向搜索，需要更新的信息：坐標、是否遍歷過、搜索到的字母位置。剪枝條件：數組越界、超出單詞長度、已搜到、位置已訪問過。注意：起始位置不能從0,0開始，需要先遍歷整個圖找出單詞首字母位置，存入隊列，再遍歷該隊列進行搜索。

class Solution {
public:int m, n, l;bool ans = false;vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};vector<vector<bool>> visited;void findans(vector<vector<char>>& board, string word, int c, int r, int point){//數組越界、超出單詞長度、不符合if (c < 0 || c >= m || r < 0 || r >= n || point >= l || ans == true || visited[c][r] == true)return;for (int i = 0; i < 4; i++){if (board[c][r] == word[point]){if (point == l-1) ans = true;int dc = dir[i][0];int dr = dir[i][1];visited[c][r] = true;findans(board, word, c + dc, r + dr, point + 1);visited[c][r] = false;}}}bool exist(vector<vector<char>>& board, string word) {m = board.size();n = board[0].size();l = word.size();queue<pair<int, int>> q;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){if (board[i][j] == word[0])q.push({i, j});}}while (!q.empty() && ans == false){visited.resize(m, vector<bool>(n, false));findans(board, word, q.front().first, q.front().second, 0);q.pop();}return ans;}
};

官方題解

官解思路與筆者一致，不贅述，這里貼一個評論區的優化方法

第一個優化

比如示例 3，word=ABCB，其中字母?B?出現了?2?次，但?board?中只有?1?個字母?B，所以肯定搜不到?word，直接返回?false。

一般地，如果?word?的某個字母的出現次數，比?board?中的這個字母的出現次數還要多，可以直接返回?false。

第二個優化

設?word?的第一個字母在?board?中的出現了?x?次，word?的最后一個字母在?board?中的出現了?y?次。

如果?y<x，我們可以把?word?反轉，相當于從?word?的最后一個字母開始搜索，這樣更多的時候一開始就匹配失敗，遞歸的總次數更少。

加上這兩個優化，就可以擊敗接近?100%?了！

心得

本質是圖搜索，知識點都是關聯的，比較多邊界條件要考慮，另外筆者的剪枝位置與官解不太一致，一個是函數開頭，一個是循環里面下一層遞歸前，應該都是一樣的，不過感覺可以的話盡量在下一層遞歸前剪枝好一點，這應該也是預剪枝和后剪枝的區別？節省時間和空間。

分割回文串

我的題解

遍歷從上一刀（初始為0）到末尾的每個位置，如果為回文，加入子解集中，一直到上一刀到末尾為止，加入總解集中。雙指針判斷是否回文。

class Solution {
public:vector<vector<string>> ans;vector<string> pre;bool isPaindrome(string s, int begin, int end){while (begin < end){if (s[begin] == s[end]){begin ++;end --;}else{return false;}}return true;}void findans(string s, int point){if (point == s.size()){ans.push_back(pre);}for (int i = point; i < s.size(); i++){if (isPaindrome(s, point, i)){pre.push_back(s.substr(point, i+1-point));findans(s, i+1);pre.pop_back();}}}vector<vector<string>> partition(string s) {if (s.empty())return {};findans(s, 0);return ans;}
};

官方題解

官解與筆者思路大致一樣，但是用了動態規劃把每個子串是不是回文串預處理了出來，大大節省時間。

class Solution {
private:vector<vector<int>> f;vector<vector<string>> ret;vector<string> ans;int n;public:void dfs(const string& s, int i) {if (i == n) {ret.push_back(ans);return;}for (int j = i; j < n; ++j) {if (f[i][j]) {ans.push_back(s.substr(i, j - i + 1));dfs(s, j + 1);ans.pop_back();}}}vector<vector<string>> partition(string s) {n = s.size();f.assign(n, vector<int>(n, true));for (int i = n - 1; i >= 0; --i) {for (int j = i + 1; j < n; ++j) {f[i][j] = (s[i] == s[j]) && f[i + 1][j - 1];}}dfs(s, 0);return ret;}
};

心得

果然一天不做就手生了，官解的動態規劃解法認真學習，有點意思！

知識點

初始化二維數組 f.assign(n, vector<int>(n, true));?

1. vector<int>(n, true)??:

   • 創建一個大小為?n?的?vector<int>（整數向量）
   • 所有元素初始化為?true（注意：true?會被隱式轉換為?int?類型的?1）

2. ??f.assign(n, ...)??:

   • 對向量?f?進行賦值操作
   • 將?f?設置為包含?n?個上述創建的?vector<int>(n, true)
   • 結果是創建一個?n × n?的二維向量，所有元素初始化為?1