131. 分割回文串https://leetcode.cn/problems/palindrome-partitioning/
https://leetcode.cn/problems/palindrome-partitioning/
給你一個字符串?s，請你將?s?分割成一些子串，使每個子串都是?回文串?。返回?s?所有可能的分割方案。
示例 1：
輸入：s = "aab" 輸出：[["a","a","b"],["aa","b"]]
示例 2：
輸入：s = "a" 輸出：[["a"]]
提示：
1 <= s.length <= 16s?僅由小寫英文字母組成
DFS方案1：初始化一個代表分割點的01數組，然后對這個數組的狀態使用dfs搜索。這個方案耗時長，空間復雜度也不小。具體代碼如下：
class Solution {
public:vector<vector<string>> ans;bool cutoff[20] = {false};//代表分割點的01數組bool check(string s)//判斷回文串{string ss = s;reverse(s.begin(),s.end());if(ss==s)return true;else return false;}void dfs(string s,int cur)//枚舉每一個位置，有在該點分割與不分割兩種情況{if(cur == s.size()){vector<string> temp;int i = 0;while(true){string t;t.push_back(s[i]);i++;while(!cutoff[i]){t.push_back(s[i]);i++;}if(!check(t))return;else temp.push_back(t);if (i >= s.size())break;}ans.push_back(temp);return;}cutoff[cur] = true;dfs(s,cur+1);cutoff[cur] = false;dfs(s,cur+1);}vector<vector<string>> partition(string s) {//為了整體代碼和諧，將首尾都設為分割cutoff[0] = true;cutoff[s.size()] = true;dfs(s,1);return ans;}
};DFS方案2：從前到后直接枚舉分割點。如下圖：
這個方案更快些，具體差別在該方案能及時排除不可能選項，而不是等上一個方案把所有可能情況全列出來然后對每個依次排除。代碼具體如下：
class Solution {
public:vector<vector<string>> ans;vector<string> temp;bool check(string s){string ss = s;reverse(s.begin(),s.end());if(ss==s)return true;else return false;}void dfs(int startindex,const string s)//前者代表起始點{if(startindex==s.size()){ans.push_back(temp);return;}for(int i = startindex;i<s.size();++i){string str = s.substr(startindex,i-startindex + 1);if(check(str)){temp.push_back(str);dfs(i+1,s);temp.pop_back();}else continue;}}vector<vector<string>> partition(string s) {dfs(0,s);return ans;}
};順便說一道幾乎一樣的題：
93. 復原 IP 地址https://leetcode.cn/problems/restore-ip-addresses/
有效 IP 地址?正好由四個整數（每個整數位于?0?到?255?之間組成，且不能含有前導?0），整數之間用?'.'?分隔。
- 例如：
"0.1.2.201"?和"192.168.1.1"?是?有效?IP 地址，但是?"0.011.255.245"、"192.168.1.312"?和?"192.168@1.1"?是?無效?IP 地址。
給定一個只包含數字的字符串?s?，用以表示一個 IP 地址，返回所有可能的有效 IP 地址，這些地址可以通過在?s?中插入?'.'?來形成。你?不能?重新排序或刪除?s?中的任何數字。你可以按?任何?順序返回答案。
示例 1：
輸入：s = "25525511135" 輸出：["255.255.11.135","255.255.111.35"]
示例 2：
輸入：s = "0000" 輸出：["0.0.0.0"]
示例 3：
輸入：s = "101023" 輸出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
1 <= s.length <= 20s?僅由數字組成
思路幾乎一致，都是要求分割的字符串所有情況，唯一不同的是這道題有些額外的條件，但都很好解決，具體代碼如下：
class Solution {
public:vector<string> ans;vector<string> temp;inline int transform(string s)//字符串轉數字{int t = 0;int re = 0;for(int i = s.size()-1;i>=0;i--,t++){re+=(s[i] - '0')*pow(10,t);}return re;}bool check(string s){string ss = s;reverse(s.begin(),s.end());if(ss==s)return true;else return false;}void dfs(int startindex,const string s)//前者代表起始點{if(temp.size()>4)//很明顯的剪枝return;if(startindex==s.size()&&temp.size()==4){string str;for(int i = 0;i<temp.size();++i){for(int j = 0;j<temp[i].size();++j){str.push_back(temp[i][j]);}str.push_back('.');}str.pop_back();ans.push_back(str);return;}for(int i = startindex;i<s.size();++i){string str = s.substr(startindex,i-startindex + 1);if((str.size()>=2&&str[0] == '0')||str.size()>3||transform(str)>255)//由題得出的篩選條件continue;temp.push_back(str);dfs(i+1,s);temp.pop_back();}}vector<string> restoreIpAddresses(string s) {dfs(0,s);return ans;}
};
