The IP Address Decomposition Problem - Compute All Valid IP Addresses From Raw IP String

Free 5-Day Mini-Course: https://backtobackswe.com Try Our Full Platform: https://backtobackswe.com/pricing 📹 Intuitive Video Explanations 🏃 Run Code As You Learn 💾 Save Progress ❓New Unseen Questions 🔎 Get All Solutions Question: You are given a raw IP address string without period separators between the digits. Return all valid IP addresses that can be created from the raw IP string where it is your job to place the periods. This is sort of a knowledge question but if you get this in an interview you'd probably get the constraints, otherwise, it is the interviewer's fault for being a bad interviewer since general SWE questions should primarily be about problem solving skills and not domain specific knowledge/facts. Whenever we hear "compute" or "generate" we know that we will have to do some sort of repeated looping or recursion in a backtracking approach. For this problem, we can do either. Approach 1 (iteration) A triple nested set of for loops where in each section we create a part of the IP string, validate that section we just snipped out and then continue on to generate the rest of the IP string Approach 2 (backtracking) The 3 Keys To Backtracking: Our Choice: - We will take snippets of substrings 1-3 characters long Our Constraints: - We cannot have a value greater than 255 or less than 0 in any subsection. - We cannot have a leading 0 in any subsection Our Goal: - Get 4 valid subsections out of the raw string that we started with that will comprise the fully valid IP recomposition We can make progress through the string, slowly decoding it in all ways possible by taking a snippet, validating it, and then continuing on in the generation path. Since we will be using recursion, each recursive call will express all possible ways to arrange a certain subsection of the string that is... Until we reach the base case which is when we have all 4 segments filled out (and by default, our index pointer has progressed to the string's length