Intermediate Level
Implement the restoreIpAddressesCount method that counts valid IP addresses that can be restored from the digits.
The input is a string digits containing only numeric characters.
Your task is to count how many valid IP addresses can be restored by inserting three dots into the string. A valid IP address has exactly four parts.
Each part must be between 0 and 255. A part cannot have leading zeros unless the part itself is exactly 0.
Example 1
Input
digits (string) =
25525511135Returns (int)
2Example 2
Input
digits (string) =
0Returns (int)
1Example 3
Input
digits (string) =
1111Returns (int)
1Use backtracking to choose four IP address segments.
At each step, try taking one, two, or three digits as the next segment. Accept the segment only if it is within 0 to 255 and does not break the leading-zero rule.
When exactly four segments are chosen and all digits are used, one valid IP address has been restored.
Pseudocode:
function restoreIpAddressesCount(digits):
count = 0
backtrack(index, parts):
if parts == 4:
if index == length of digits:
count++
return
for length from 1 to 3:
if index + length > length of digits:
break
segment = substring of digits from index with given length
if segment has leading zero and length > 1:
continue
if numeric value of segment > 255:
continue
backtrack(index + length, parts + 1)
backtrack(0, 0)
return countReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run