DFS with backtracking Java


  • 0
    T

    Note : This solution is time inefficient . The purpose of this solution is to get you to understand how backtracking would work and it is also for those who couldn't come up with any solution to this problem.

    This is raw backtracking.

    public class Solution {
        public List<String> restoreIpAddresses(String s) {
            final int MAX_LENGTH_POSSIBLE = 12;
            List<String> list = new ArrayList<>();
            if(s==null || s.isEmpty()) return list;
            
            if(s.length()>MAX_LENGTH_POSSIBLE) return list; 
            
            List<List<String>> result = new ArrayList<>();
            helper(0, s, "", 0, list);
            return list;
        }
        
    // dots parameter represent the dot number we are planning to add in this iteration. Meaning if we are planning to add dot 4, then we already have 3 dots added.
        private void helper(int index, String s, String t, int dots, List<String> list ){
            if(index == s.length()){
                if(dots == 4){
                    list.add(t);
                }
                return;
            }
            
            for(int len = 1;len<s.length();len++){
                if(index+len>s.length()) return; // if we are out any more numbers to append
                String temp = s.substring(index, index+len);
                if(Integer.parseInt(temp)>255 || (temp.length()>1 && s.charAt(index)=='0')) return; // if we are forming a number greater than 255
                
                helper(index+len, s, dots == 3 ? t+temp : t+temp+".", dots+1, list);
                
            }
        }
    }

Log in to reply
 

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