Leetcode93. Restore IP Addresses复原IP地址

给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

示例:

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

题目很简单但是，需要特定判断的情况很多。

思路可以是递归和多重循环，。

因为该题没有太需要用到递归，所以直接用循环。

易错的地方会在代码中标注。

  class Solution

  {

  public:

	  vector<string> restoreIpAddresses(string s)

	  {

		  vector<string> res;

		  int len = s.size();

		  ///第一次

		  for (int i = 1; i <= 3; i++)

		  {

			  //判断是否超过了字符串的长度，除了最后一次，都要需要判断

			  if (i >= len)

				  continue;

			  string str1 = string(s.begin(), s.begin() + i);

			  //检查字符串是否符合要求

			  if (!Check(str1))

				  continue;

			  ///第二次

			  for (int j = 1; j <= 3; j++)

			  {

				  if (i + j >= len)

					  continue;

				  string str2 = string(s.begin() + i, s.begin() + i + j);

				  if (!Check(str2))

					  continue;

				  ///第三次和第四次

				  for (int k = 1; k <= 3; k++)

				  {

					  if (i + j + k >= len)

						  continue;

					  string str3 = string(s.begin() + i + j, s.begin() + i + j + k);

					  if (!Check(str3))

						  continue;

					  string str4 = string(s.begin() + i + j + k, s.end());

					  if (!Check(str4))

						  continue;

					  res.push_back(str1 + '.' + str2 + '.' + str3 + '.' + str4);

				  }

			  }

		  }

		  return res;

	  }

	  bool Check(string s)

	  {

		  //检测最后一个字符串str4是否为空

		  if (s.size() == 0)

			  return false;

		  //判断是否有011,01这种以0开头的字符串

		  if (s[0] == '0' && s.size() > 1)

			  return false;

		  int number = 0;

		  for (int i = 0; i < s.size(); i++)

		  {

			  number = number * 10 + (s[i] - '0');

			  //需要在里面进行判断是否超出范围

			  //因为number是字符串转来的，很可能超出了int的范围，超出后变成负数判断就比255小，返回true，显然这是不正确的

			  //所以在循环里面提前判断

			  if (number > 255)

				  return false;

		  }

		  return true;

	  }

  };

巴特西

Leetcode93. Restore IP Addresses复原IP地址

最新文章

热门文章