Backtracking (exploration and backtracking) is a selection search method, also known as heuristics, which searches forward according to the selection criteria to achieve the goal. However, when a certain step is explored, it is found that the original choice is not good or fails to reach the target, so it takes a step back to make a new choice. The technology of going back and going again when there is no way is called backtracking method, and the point in a certain state that meets the backtracking condition is called “backtracking point”.

It’s a recursive algorithm, but there’s a caveat:

  • Preserve the scene, while recursing, save the last state, recursion can still return to the last state
  • End the condition and save the result when the condition is met

The title

Given a string containing only numbers, undo it and return all possible IP address formats.

Example:

Input:"25525511135"Output:"255.255.11.135"."255.255.111.35"]
Copy the code

answer

I do algorithm questions are not many, but personal experience, in the time to do the best manual drawing on paper, simulation of the program to run the map.

  • A blank sheet of paper
  • Draw carefully

But maybe it’s more convenient to draw on a computer, so let’s think about what the path should be. As shown in figure:

Qualifying conditions:

  • Because it is an IP address, the number cannot be greater than 255 or less than 0
  • As you can see from the graph, the IP address is at layer 3.
  1. So let’s think about the general variables.
  • The hierarchy
  • Current string
  • Remaining string
  • Save a collection of results
  1. Write down the conditions that stop recursion
private void restoreAddressNew(String source, String currentStr, Integer currentLevel, Integer offset, List<String> res) {
	if (currentLevel == 3) {
            if (isValidNew(source.substring(offset))
                    ) {
                res.add(currentStr + "." + source.substring(offset));
            }
            return; }... }Copy the code
  1. Write a function that checks whether a segment in a valid IP address is valid
    private boolean isValidNew(String str) {
        if (str.length() == 0 || str.length() > 3 || Integer.parseInt(str) < 0 || Integer.parseInt(str) > 255
                || (str.startsWith("0") && str.length() > 1)) {return false;
        }
        return true;
    }
Copy the code
  1. Write the conditions for recursion
private void restoreAddressNew(String source, String currentStr, Integer currentLevel, Integer offset, List<String> res) {
        if (currentLevel == 3) {

            if (isValidNew(source.substring(offset))
                    ) {
                res.add(currentStr + "." + source.substring(offset));
            }
            return;
        }

    	/ / the recursion
        for (int i = 1; i <= 3; i++) {
            if (offset > source.length() || (offset + i) > source.length()) {
                return;
            }
            String seg = source.substring(offset, offset + i);
            // Save the original state
            String oldStr = currentStr;
            
            // Prevent addresses beginning with "."
            if (currentStr.length() == 0) {
                currentStr = seg;
            } else {
                currentStr = currentStr + "." + seg;
            }
            if (isValidNew(seg)) {
                restoreAddressNew(source, currentStr, currentLevel + 1, offset + i, res);
                // Restore status after processingcurrentStr = oldStr; }}}Copy the code
  1. If there is uncertainty, it can output the current state and judge the current result
  2. Complete scheme
public class RestoreIPAddress {

    public static void main(String[] args) {
        List<String> strings = new RestoreIPAddress().restoreIpAddressesNew("25525511135");
    }

    private List<String> restoreIpAddressesNew(String s) {
        List<String> result = new ArrayList<>();
        restoreAddressNew(s, "".0.0, result);
        return result;
    }

    
    private void restoreAddressNew(String source, String currentStr, Integer currentLevel, Integer offset, List<String> res) {
        if (currentLevel == 3) {

            if (isValidNew(source.substring(offset))
                    ) {
                res.add(currentStr + "." + source.substring(offset));

            }
            return;
        }

        for (int i = 1; i <= 3; i++) {
            if (offset > source.length() || (offset + i) > source.length()) {
                return;
            }
            String seg = source.substring(offset, offset + i);
            String oldStr = currentStr;
            if (currentStr.length() == 0) {
                currentStr = seg;
            } else {
                currentStr = currentStr + "." + seg;
            }
            if (isValidNew(seg)) {
                restoreAddressNew(source, currentStr, currentLevel + 1, offset + i, res); currentStr = oldStr; }}}private boolean isValidNew(String str) {
        if (str.length() == 0 || str.length() > 3 || Integer.parseInt(str) < 0 || Integer.parseInt(str) > 255
                || (str.startsWith("0") && str.length() > 1)) {return false;
        }
        return true; }}Copy the code

Mistakes made in the middle

  • The first time you forget to save the scene, there’s a data fight, and the data is weird
  • There was an address condition beginning with a “.”

Is to think that the problem is not comprehensive enough, the program runs fast, people calculate slowly, but the rules of the program is defined by people. Only if you can figure out the rules, can you guide the computer to do the right thing, otherwise when you are confused, the program will not run correctly.

The last

Drawing is a great thing to help clear your mind. Take your time. Take your time

reference

  • LeetCode questions 93