复制 IP 地址
给定一个只包含数字的字符串, 复原它并返回所有可能的 IP 地址格式.
示例:
输入: "25525511135"
输出: ["255.255.11.135", "255.255.111.35"]
- import java.util.ArrayList;
- import java.util.List;
- class Solution {
- private List<String> result = new ArrayList<>();
- int length;
- public List<String> restoreIpAddresses(String s) {
- length = s.length();
- int[] ip = new int[4];
- restoreIpAddresses(s,0,ip,0);
- return result;
- }
- private void restoreIpAddresses(String s, int si, int[] ip, int pi) {
- int sl = length - si , pl = 3 - pi , i = -1;
- String pfx = null;
- while (si<length){
- int num = s.charAt(si++) - '1' + 1;
- if (i==0) break;
- i = i == -1 ? num : i * 10 + num;
- sl--;
- if (i>255) break;
- if (sl <pl || sl> pl * 3) continue;
- if (pi==3){
- if (pfx==null){
- StringBuilder pfxBuilder = new StringBuilder();
- for (int j = 0; j < ip.length-1; j++) pfxBuilder.append(ip[j]).append('.');
- pfx = pfxBuilder.toString();
- }
- result.add(pfx + i);
- }
- ip[pi] = i;
- restoreIpAddresses(s,si,ip,pi+1);
- }
- }
- }
来源: http://www.bubuko.com/infodetail-2894123.html