LeetCode，leetcode 93.復原IP地址 dfs解法

2023-11-18 阅读 29 评论 0

摘要：給定一個只包含數字的字符串，復原它并返回所有可能的 IP 地址格式。 LeetCode、示例: 輸入: "25525511135" 輸出: ["255.255.11.135", "255.255.111.35"] 注：這里是IPV4,用2進制表示的話要32位，用10進制則是4個整數,每個整數大于

給定一個只包含數字的字符串，復原它并返回所有可能的 IP 地址格式。

LeetCode、示例:

輸入: "25525511135"
輸出: ["255.255.11.135", "255.255.111.35"]

注：這里是IPV4,用2進制表示的話要32位，用10進制則是4個整數,每個整數大于等于0小于256，不了解的話請看百度百科

代碼：

class Solution {
public:vector<string>ans;vector<string> restoreIpAddresses(string s) {string path;dfs(s,0,0,path);return ans;}void dfs(string& s,int pos,int k,string path)  // pos表示當前位置,k有幾個數了{if(pos == s.length()){if(k == 4){ans.push_back(path.substr(1));return ;}}if(k > 4) return ;if(s[pos] == '0') dfs( s, pos + 1, k + 1, path += ".0");else{int t = 0;for(int i = pos; i < s.length(); i++){    t = t * 10 + s[i] - '0';if(t < 256)  dfs( s, i+1, k+1,path + '.' + to_string(t));elsebreak;}}}
};