Restore IP address [standard backtracking + standard pruning]

Preface

Restore IP Address , Standard backtracking search , because IP Address qualification , Standard pruning practice .

One 、 Restore IP Address

Two 、 Backtracking search + Multiple pruning + common bug

package everyday.medium;

import java.util.LinkedList;
import java.util.List;

//  Restore IP Address 
public class RestoreIpAddresses {
    
    /* target: Give a string s, Split into 4 block , See if it's legal IP Address .  legal IP Address ：1：0-255;2： Only 4 Additional copies ;3： except 0 No leading is 0 Number of numbers . */
    public List<String> restoreIpAddresses(String s) {
    
        List<String> ans = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        //  enumeration   Fill in qualified IP
        dfs(s, 0, 0, sb, ans);
        //  Return to the filled list 
        return ans;
    }

    private void dfs(String s, int cur, int n, StringBuilder sb, List<String> ans) {
    
        if (n == 4 && cur == s.length()) {
    
            //  Can get here , All meet the conditions IP Address .
            sb.deleteCharAt(sb.length() - 1);
            ans.add(new String(sb));
            // bug2: hold  .  Deleted , Add it without adding it , During backtracking, there will be deletion of too many items .
            sb.append('.');
            return;
        }
        //  If you haven't run out of numbers , And it has been divided into four parts , prune ; If not 4 Share , But the numbers are useless , prune .
        if (n == 4 || cur == s.length()) return;
        //  If  s.length() - (4 - n) * 4 > 0 when , It is impossible to form IP, prune .
        // bug1:s.length() Never change , So there will be >0 advance return The situation of , Should be s.length() - cur - 1
        if (s.length() - cur - 1 - (4 - n) * 4 > 0) return;

        //  Standard backtracking 
        for (int i = 0; i < 3 && i + cur < s.length(); i++) {
    // IP  The length is less than 3 position , prune .
            //  Leading to 0, That can only be 0.
            if (i == 0 && s.charAt(cur) == '0') {
    
                sb.append("0.");
                dfs(s, cur + 1, n + 1, sb, ans);
                sb.delete(sb.length() - 2, sb.length());
                break;
            }
            //  Leading non 0
            String str = s.substring(cur, cur + i + 1);
            int len = str.length();
            int val = Integer.parseInt(str);
            if (val <= 255) {
    
                sb.append(val).append('.');
                dfs(s, cur + i + 1, n + 1, sb, ans);
                sb.delete(sb.length() - len - 1, sb.length());
            }
        }
    }

    public static void main(String[] args) {
    
        new RestoreIpAddresses().restoreIpAddresses("25525511135");
    }
}

summary

1） Backtracking search + Standard pruning + Common backtracking bug

reference

[1] LeetCode Restore IP Address