LeetCode: Restore IP Address

题目

https://oj.leetcode.com/problems/restore-ip-addresses/

分析

这道题和八皇后类似，采用回溯法来解决，也就是剪枝过的DFS。

代码

class Solution
{
public:
 vector<string> restoreIpAddresses(string s)
 {
  s_ = s;
  helper("", 1, 0);

  return res_;
 }

 void helper(string ip, int segment_num, int index)
 {
  if (segment_num == 4)
  {
   string ip_segment = s_.substr(index, s_.size() - index);
   if (!ip_segment.empty() && ip_segment.length() <= 3 
     && isValid(ip_segment))
   {
    ip += ip_segment;
    res_.push_back(ip);
   }
  }
  else
  {
   for (int i = 1; i <= 3 && i <= s_.size() - index; i++)
   {
    string ip_segment = s_.substr(index, i);
    if (isValid(ip_segment))
     helper(ip + ip_segment + '.', segment_num + 1, index + i);
   }
  }
 }

 bool isValid(string ip_segment)
 {
  if (ip_segment[0] == '0')
   return (ip_segment == "0");
  if (stoi(ip_segment) <= 255)
   return true;
  else
   return false;
 }

private:
 string s_;
 vector<string> res_;
};