Concise Java Solution: Backtracking


  • 0
    P
    public class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> result = new ArrayList<String>();
            List<Integer> list = new ArrayList<Integer>();
            dfs(s,result,list,0,4);
            return result;
        }
        
        public boolean isValid(String s) {
            if (s.length() > 3 || s.length() == 0)
                return false;
            if (s.length() > 1 && s.charAt(0) == '0')
                return false;
            if (s.length() == 3 && Integer.parseInt(s) > 255)
                return false;
            return true;
        }
        public void dfs(String s, List<String> result, List<Integer> list, int index, int remain){
            if(remain==1){
                String cur = s.substring(index,s.length());
                if(!isValid(cur)){
                    return;
                }
                int tmp = Integer.parseInt(cur);
                String str = "";
                for(int i:list){
                    str+=i+".";
                }
                str+=tmp;
                result.add(str);
            }else{
                for(int i=1;i<4;i++){
                    int end = index+i;
                    if(end>=s.length()){
                        break;
                    }
                    String cur = s.substring(index,end);
                    if(!isValid(cur)){
                        continue;
                    }
                    int tmp = Integer.parseInt(cur);
                    list.add(tmp);
                    dfs(s,result,list,end,remain-1);
                    list.remove(list.size()-1);
                    
                }
            }
        }
    }

Log in to reply
 

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