Accepted Java Backtracking solution


  • 0
    A
    public class Solution {
           List<String> solution;
        
        public List<String> restoreIpAddresses(String s) {
            solution = new ArrayList<String>();
            int[] positions = new int[3];
            backTrack(s, positions, 0);
            return solution;
        }
        
        private void backTrack(String s, int[] positions, int k) {
            if (k == 3) {
                if (isValid(s, positions)) {
                    solution.add(generateString(s, positions));
                }
            }
            else {
                List<Integer> nextMoves = getNextPositions(s, positions, k);
                for (Integer move : nextMoves) {
                    positions[k] = move;
                    backTrack(s, positions, k + 1);
                }
            }
        }
        
        private List<Integer> getNextPositions(String s, int[] positions, int k) {
            int base = (k > 0) ? positions[k - 1] : 0;
            List<Integer> result = new ArrayList<Integer>();
            if (base < s.length() && s.charAt(base) == '0') {
            	result.add(base + 1);
            	return result;
            }
            for (int i = 1 ; i < 3; i++) {
                if (i + base < s.length()) {
                    result.add(i + base);
                }
            }
            if (base + 3 < s.length() && Integer.parseInt(s.substring(base, base + 3)) <= 255) {
                result.add(base+3);
            } 
            return result;
        }
        
        private boolean isValid(String s, int[] positions) {
            int lastLength = s.length() - positions[2];
            if (lastLength <= 3 && lastLength > 0) {
            	String sLast = s.substring(positions[2], s.length());
                int lastPart = Integer.parseInt(sLast);
                return (lastPart <= 255 && String.valueOf(lastPart).equals(sLast));
            }
            return false;
        }
        
        private String generateString(String s,  int[] positions) {
            int prevIdx = 0;
            StringBuilder sb = new StringBuilder();
            for (int i = 0 ; i < 3; i++) {
                sb.append(s.substring(prevIdx, positions[i])).append(".");
                prevIdx = positions[i];
            }
            sb.append(s.substring(prevIdx, s.length()));
            return sb.toString();
        }
    }

Log in to reply
 

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