My Java DFS code


  • 0
    public class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> result = new ArrayList<String>();
            if (s == null || s.length() < 4 || s.length() > 12) {
                return result;
            }
            
            dfs(result, "", s, 0);
            return result;
        }
        
        private void dfs(List<String> result, String temp, String s, int start) {
            if (temp.length() == s.length() + 4) {
                if (start == s.length()) {
                    result.add(temp.substring(0, temp.length() - 1));
                }
                return;
            }
            
            for (int len = 1; start + len <= s.length() && len <= 3; len++) {
                String attempt = s.substring(start, start + len);
                if (isValid(attempt)) {
                    dfs(result, temp + attempt + '.', s, start + len);
                }
            }
        }
        
        private boolean isValid(String attempt) {
            if (attempt.charAt(0) == '0') {
                return attempt.equals("0");
            }
            
            int value = Integer.parseInt(attempt);
            return value >= 0 && value <= 255;
        }
    }
    

Log in to reply
 

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