My concise recursive 2ms solution beats 97%


  • 0
    S
    public List<String> restoreIpAddresses(String s) {
         List<String> res = new ArrayList<>();
         helper(res, new StringBuilder(), s, 0, 1);
         return res;
    }
    	
    private void helper(List<String> res, StringBuilder sb, String s, int id, int p) {
         if (p > 4){
              res.add(sb.toString().substring(0, sb.length()-1));
              return;
         }
         for (int i = 1; i <= 3; i++) {
              int rem = s.length()-id-i;
              if (rem < 4-p || rem > 3*(4-p)) continue;
              String sub = s.substring(id, id+i);
              if (sub.length()>1 && sub.charAt(0) == '0' || Integer.parseInt(sub)>255 ) break;
              sb.append(sub).append('.');
              helper(res, sb, s, id+i, p+1);
              sb.delete(sb.length()-i-1, sb.length());
         }
    }
    

Log in to reply
 

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