LeetCode93 Restore IP Addresses

题目：

Given a string containing only digits, restore it by returning all possible valid IP address combinations. （Medium）

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

分析：

使用回溯法即可。helper函数用来处理DFS过程，isValid判断一个子串是否符合IP地址一个点分十进制的一块。

注意在isValid中要除去类似00，01这种0打头的情况。

代码：

 class Solution {

 private:

     vector<string> result;

     bool isValid(const string& s) {

         if (s[] == '' && s.size() > ) {  // for case like "00.122.122.122"

             return false;

         }

         int num = stoi(s);

         if (num >=  && num <= ) {

             return true;

         }

         return false;

     }

     void helper(const string& s, string curS, int start, int step) {

         if (step == ) {

             if (start != s.size()) {

                 return;

             }

             curS.pop_back();

             result.push_back(curS);

             return;

         }

         for (int i = ; i <= ; ++i) {

             if (start + i <= s.size()) {

                 string tempS = s.substr(start, i);

                 if (isValid(tempS)) {

                     string newS = curS + tempS;

                     newS.push_back('.');

                     helper(s, newS, start + i, step + );

                 }

             }

         }

     }

 public:

     vector<string> restoreIpAddresses(string s) {

         string curS;

         helper(s, curS, , );

         return result;

     }

 };

巴特西

LeetCode93 Restore IP Addresses

最新文章

热门文章