前面兩篇內容我們都是在做有關回溯問題的組合應用
今天的題目主題是：回溯法在切割問題的應用
題目一：分割回文串
問題描述
131. 分割回文串 - 力扣（LeetCode）
給你一個字符串?s，請你將?s?分割成一些?子串，使每個子串都是?回文串?。返回?s?所有可能的分割方案。
示例 1：
輸入：s = "aab" 輸出：[["a","a","b"],["aa","b"]]
示例 2：
輸入：s = "a" 輸出：[["a"]]
提示：
1 <= s.length <= 16s?僅由小寫英文字母組成
解題步驟
在做這題之前我們需要明確回文串是什么東西👇
那么我們解決這個問題就可以分為分割字符串和判斷回文串兩個part
運用回溯法分割字符串其實和組合問題是類似的思路
我們需要按照字符串順序，在所有可能位置砍上一刀，形成不同的字符串碎片
那么為了不錯過任何一種可能，就需要按順序遍歷
下面就來嘗試使用回溯三部曲！
1.確定函數返回值及參數
依舊使用backtracking這個名字，沒有返回值的要求，參數呢傳入我們需要使用的字符串s以及一個開始索引startindex即可
這個開始索引是不斷變大的，意味著每次砍第一刀下去，第一個碎片的長度在慢慢變大，這也是我們有序分割的重要環節
void backtracking(string s,int startindex)
2.確定終止條件
按照最簡單的思路，和之前的組合問題一樣，我們會在葉子結點取到該過程的一個答案，再做個對應題目限制的判斷，合適就加入result中，?
那么我們的分割也是這樣，在葉子節點結束分割，把整個字符串剁碎了，
但需要注意的是，在葉子節點我們得到的不是碎片，而是雖然碎了但仍舊可以拼成完整s的組合體
就像你買了一只烤鴨，咔咔剁了幾刀，你拿到手的是所有鴨子碎片而不是只有一個鴨屁股
那么在這種情況下，加入判斷回文子串的代碼好像有點不方便
所以我們改為在單層遞歸的時候做判斷而不是在終止條件做判斷
這樣做同時也更省事了，如果你切了一刀發現這個不是回文串就沒必要再切下去了
就好比切到鴨屁股的話扔掉就好了，沒必要把鴨屁股也剁碎留著
還有一點需要明確的是分割完畢的表示方法，
在參數列表中我們不斷傳遞的startindex實際上就對應我們砍下去的那一刀，
那么只要這個索引大于等于回文串長度就是切完了
if(startindex>=s.size()){
? ? ? ? result.push_back(path);
? ? ? ? return;
}
?3.確定單層遍歷操作
還是同樣的邏輯，最外層確定第一刀位置
切下來以后加入path中，再遞歸切第二刀...
遞歸結束后需要pop加入值，做一個回溯
除了以上切割操作，我們還需要加入判斷回文串的代碼
這一個部分為使效率最大化可以加在把碎片加入path的代碼前
也就是說符合回文才加入path，否則直接return
判斷回文串我們可以另設函數所以單層遍歷操作應該如下:
for(int i=startindex;i<s.size();i++){
? ? ? ? if(isPalindrome(...){//這個函數等會再想！
? ? ? ? ? ? ? ? string str = s.substr(startindex,i-startindex+1);//當前碎片是【startindex,i】
? ? ? ? ? ? ? ? path.push_back(str);//是回文串！切下來放進path中！
? ? ? ? }else{
? ? ? ? ? ? ? ? continue;//不是就跳出！
? ? ? ? }
? ? ? ? backtracking(s,i+1);
? ? ? ? path.pop_back();
}? ? ? ?
補充：
s.substr(pos, len)
substr()是C++語言函數，主要功能是復制子字符串，要求從指定位置開始，并具有指定的長度。如果沒有指定長度_Count或_Count+_Off超出了源字符串的長度，則子字符串將延續到源字符串的結尾。?
?ok那么回溯算法的步驟我們已經完成了，還剩下判斷回文串的邏輯需要寫
4.判斷回文串
按照回文串的概念，我們只需要一個指針從頭開始，一個指針從尾開始
不斷同頻比較兩個字符是否相等就可以了
那么需要的參數就是這個字符串碎片
返回值設為bool類型
bool isPalindrome(string s,int start,int end){
? ? ? ?for(int i=start,j=end;i<j;i++,j--){
? ? ? ? ? ? ? ? if(s[i] !=s[j]){
? ? ? ? ? ? ? ? ? ? ? ? return false;
? ? ? ? ? ? ? ? }
????????}
? ? ? ? return true;
}
合并所有代碼，并在主函數中傳參調用即可！完整代碼看下面👇！?
code
class Solution {
public:vector<string> path;vector<vector<string>> result;bool isPalindrome(string s,int start,int end){for(int i=start,j=end;i<j;i++,j--){if(s[i]!=s[j]){return false;}}return true;}void backtracking(string s,int startindex){if(startindex>=s.size()){result.push_back(path);return;}for(int i=startindex;i<s.size();i++){if(isPalindrome(s,startindex,i)){string str=s.substr(startindex,i-startindex+1);path.push_back(str);}else{continue;}backtracking(s,i+1);path.pop_back();}}vector<vector<string>> partition(string s) {backtracking(s,0);return result;}
};題目二：復原IP地址
問題描述
93. 復原 IP 地址 - 力扣（LeetCode）
有效 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?僅由數字組成
解題步驟
參照上一題，我一開始寫了以下代碼，
主要思路就是無情分割，直到最后，
在每一步分割中使用函數判斷是否符合要求
合理就加入path，逐漸組成IP地址
最后在葉子節點處加入正確的IP到result中
但是發現在單層遞歸中很難處理，
所以我們需要改變一下整個回溯的過程，按照這個題目的特點，給出量身定制的方案
class Solution {
public:
? ? string path;
? ? vector<string> result;
? ? bool isOK(string str){
? ? ? ? if(str.empty() || str.size()>3 || str[0]=='0'){
? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? int num=stoi(str);
? ? ? ? return num>=0&&num<=255;
? ? }
? ? void backtracking(string s,int startindex){
? ? ? ? if(startindex>=s.size()){
? ? ? ? ? ? result.push_back(path);
? ? ? ? ? ? return;
? ? ? ? }
? ? ? ? for(int i=startindex;i<s.size();i++){
? ? ? ? ? ? string str=s.substr(startindex,i-startindex+1);
? ? ? ? ? ? if(isOK(str)){
? ? ? ? ? ? ? ? path+=str;
? ? ? ? ? ? ? ?//@#@￥￥#%#！@@￥#@%！@？？？？？
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? ? ? backtracking(s,i+1);
? ? ? ? ? ? path.pop_back();
? ? ? ? }
? ? }
? ? vector<string> restoreIpAddresses(string s) {
? ? ? ? if(s.size()<4 || s.size()>12){
? ? ? ? ? ? return result;
? ? ? ? }
? ? ? ? backtracking(s,0);
? ? ? ? return result;
? ? }
};
?再審審題！
IP地址是只能有4段的，每一段不超過3個數字，
所以這里我們需要把段數作為切割完成的標志，不能再用索引指到最后，
這樣就相當于做數學證明題有條件沒用上，那一般來說都是證不出來的！！！
那么和段數有關的還有IP地址中的 '.' （點），
為了一舉兩得（實現判斷段數和加點）我們可以用點數來代表段數，
點數為3意味著段數為4嘛！
重新走一邊回溯三部曲
1.確定函數返回值及參數
按照上面的思路，我們得加入段數作為參數，搭配startindex共同表示分割情況
startindex關乎下刀點，不能丟掉，把刀丟了還怎么切嘛！
void backtracking(string s,int startindex,int pointnum)
2.確定終止條件
上面已經捋清楚了:點數為3意味著段數為4
但是加入第三個點后我們還沒有判斷剩下部分，也就是第四段是否符合要求
所以這個最后一部分的合法性要放在這個終止條件中進行判斷
合法后再加入到result中
if(pointnum==3){
? ? ? ? if(isValid...){//判斷合法性等會再說！
? ? ? ? ????????result.push_back(s);
????????}
????????return;? ? ??
}
?3.確定單層遍歷操作
在單層遍歷中我們需要往s中加點(題目說了可以通過在?s?中插入?'.'?來形成)，修改pointnum，遞歸，回溯
最外層遍歷依舊代表第一刀（或者說上一刀）的位置，
這樣才能確保第二🔪是從剩下的部分切的
切下來一段就需要判斷是否合法
如果合法，在s的這個位置后面加上點
再讓pointnum+1
遞歸backtracking函數
pointnum回溯，
s回溯
如果不合法，那么直接結束
for(int i=startindex;i<s.size();i++){
? ? ? ? if(isValid...){
? ? ? ? ? ? ? ? s.insert(s.begin()+i+1,'.');//加點
? ? ? ? ? ? ? ? pointnum++;
? ? ? ? ? ? ? ? backtracking(s,i+2,pointnum);//加入點后要再后挪一位！
? ? ? ? ? ? ? ? pointnum--;
? ? ? ? ? ? ? ? s.erase(s.begin()+i+1);
? ? ? ? }
? ? ? ? else
? ? ? ? ? ? ? ? break;
}
4.編寫判斷合法性函數
作為一個判斷類的函數，返回值肯定是bool類型，
參數是為了傳入待判斷的片段，所以依舊是s，start，end
在函數體中利用if?判斷IP地址一段的數字區間是否在[0,255],每一段開頭第一個是否為0，區間長度是否小于等于3,該片段是否為空
否就返回false，都沒有踩雷就返回true
bool isValid(string& s,int start,int end){? ?
????????if (start > end || end - start + 1 > 3) {
? ? ? ? ? ? return false; // 片段為空或長度超過3
? ? ? ? }
? ? ? ? if (s[start] == '0' && start != end) {
? ? ? ? ? ? return false; // 前導0不合法
? ? ? ? }
? ? ? ? string str = s.substr(start, end - start + 1);
? ? ? ? int num = stoi(str);
? ? ? ? return num >= 0 && num <= 255;
}????????
?最后整合代碼，傳入對應參數，在主函數中調用即可，
此外，在主函數中還可以加入一個剪枝，
如果字符串長度明顯不符合IP地址的長度就不用調用回溯算法了
if(s.size()<=0 || s.size()>12)
? ? ? ? return result;
完整代碼在下方！?
code?
class Solution {
public:vector<string> result;bool isValid(string& s,int start,int end){if (start > end || end - start + 1 > 3) {return false; // 片段為空或長度超過3}if (s[start] == '0' && start != end) {return false; // 前導0不合法}string str = s.substr(start, end - start + 1);int num = stoi(str);return num >= 0 && num <= 255;}?????void backtracking(string s,int startindex,int pointnum){if(pointnum==3){if(isValid(s,startindex,s.size()-1)){//最后一段！result.push_back(s);}return;}for(int i=startindex;i<s.size();i++){if(isValid(s,startindex,i)){s.insert(s.begin()+i+1,'.');//加點pointnum++;backtracking(s,i+2,pointnum);pointnum--;s.erase(s.begin()+i+1);}elsebreak;}}vector<string> restoreIpAddresses(string s) {if(s.size()<=0 || s.size()>12)return result;backtracking(s,0,0);return result;}
};
)
