本文主要是介绍* Leetcode 93. Restore IP Addresses,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
https://leetcode.com/problems/restore-ip-addresses/description/
简单dfs,结合具体ip的格式要求剪枝即可
class Solution {
public:vector<string> restoreIpAddresses(string s) {vector<string> ans;string prefix = "";dfs(s, 0, 0, prefix, ans);return ans;}bool legal(string s) {if ( s[0] == '0' && s.size() > 1 ) return false;return ( stoi(s) <=255 );}void dfs(string ip, int cur, int already_cnt, string prefix, vector<string> &ans) {if (cur >= ip.size()) {return ;}for (int i = 0; i < 3; i++) {if (cur + i >= ip.size() )continue;string seg = ip.substr(cur, i+1);if (legal(seg)) {if (already_cnt == 3) {string one_ans = prefix + seg;if (one_ans.size() == ip.size() + 3)ans.push_back(prefix + seg);} else {dfs(ip, cur + i + 1, already_cnt + 1, prefix + seg + '.', ans);}}}}};
这篇关于* Leetcode 93. Restore IP Addresses的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!