using System; using System.Collections.Generic; using System.Text; public partial class Solution { public IList RestoreIpAddresses(string s) { IList result = new List(); if (string.IsNullOrEmpty(s)) return result; if (s.Length < 4 || s.Length > 12) return result; Backtrack(result, s, 0, new StringBuilder(), 0); return result; } private void Backtrack(IList candidates, string numbers, int segPos, StringBuilder curr, int numSegments) { if (numSegments == 4) { candidates.Add(curr.ToString()); return; } if (numSegments == 2 && numbers.Length - segPos > 6) return; if (numSegments == 3 && numbers.Length - segPos > 3) return; for(int tries = 0; tries < 3; tries++) { int nextPos = tries + 1; if (segPos + nextPos > numbers.Length) break; if (numSegments == 3 && segPos + nextPos != numbers.Length) continue; string newSegment = numbers.Substring(segPos, nextPos); if (!IsSegmentValid(newSegment)) continue; curr.Append(newSegment); if (numSegments + 1 != 4) curr.Append('.'); Backtrack(candidates, numbers, segPos + nextPos, curr, numSegments + 1); curr.Length -= newSegment.Length; if (numSegments + 1 != 4) curr.Length -= 1; } } private bool IsSegmentValid(string s) { if (string.IsNullOrEmpty(s)) return false; if (s.Length < 0 || s.Length > 3) return false; int intVal; if (!int.TryParse(s, out intVal)) return false; if (intVal.ToString().Length != s.Length) return false; // example: "000" converted to 0 return intVal >= 0 && intVal <= 255; } static void Main() { string testString; testString = Console.ReadLine(); Solution sol = new Solution(); IList res = sol.RestoreIpAddresses(testString); foreach (var p in res) { Console.WriteLine(p); } } }