Java solution using backtracking


  • 0
    A

    public class Solution {

    public static List<String> restoreIpAddresses(String s) {
        int[] octect = new int[4];
        int octIdx = 0;
        List<String> validIps = new ArrayList<>();
        int k = 0;
        backtrack(octect, octIdx, k, s, validIps);
        return validIps;
    }
    
    private static void backtrack(int[] octects, int octIdx, int k, String s, List<String> validIps) {
        if(octIdx == 4) {
            if(k == s.length()) {
                StringBuilder sb = new StringBuilder();
                sb.append(octects[0]);
                for(int x=1;x<octects.length;x++) {
                    sb.append("." + octects[x]);
                }
               validIps.add(sb.toString());
            }
            return;
        }
    
        for(int x=1;x<=s.length()-k;x++) {
            String substr = s.substring(k, k+x);
            int octect = Integer.parseInt(substr);
            if(octect <= 255) {
                octects[octIdx] = octect;
                backtrack(octects, octIdx + 1, k+x, s, validIps);
                if(octect == 0) {
                    break;
                }
            }
            else {
                break;
            }
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.