<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}
/* 設定連結 */
a,
.open-files-container li.selected a {
color: #89FFF8;

}
a:hover,
.open-files-container li.selected a:hover {
color: #89FFF890;
}

</style>

###### tags: `Leetcode`

# 93. Restore IP Addresses

###### Link : https://leetcode.com/problems/restore-ip-addresses/description/

## 題目
回傳所有可能的IP地址
## 程式碼

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> ans;
        Backtracking(s, 0, 0, ans);
        return ans;
    }
    private:
    void Backtracking(string &s, int start, int end, vector<string> &ans){
        //切割出的數字已經大於三個 不需繼續算下去
        if(count(s.begin(), s.end(), '.') > 3)
            return;
        if(s.size() <= end){//走訪string完畢
            //確認數字剛好有三個 才放入答案中
            if(count(s.begin(), s.end(), '.') == 3 && s.back()!='.')
                ans.push_back(s);
            return;
        }
        //目前數字是兩位數以上且開頭是0，不需繼續算下去
        if(s[start] == '0' && start < end)
            return;
        //目前數字大於255，不需繼續算下去
        if(stoi(s.substr(start, end - start + 1)) > 255)
            return;
        else{//Backtracking
            //目前數字後面加上.
            s.insert(end + 1, ".");
            Backtracking(s, end + 2, end + 2, ans);
            //目前數字後面不加上.
            s.erase(end + 1, 1);
            Backtracking(s, start, end + 1, ans);
        }
    }
};

## Date
### 2023/1/21