Basic Backtracking Solution --- Java


  • 0
    T
      public class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> ans = new ArrayList<>();
            if (s == null || s.length() == 0) {
                return ans;
            }
            
            String path = "";
            int start = 0, times = 0;
            helper(ans, path, start, times, s);
            
            return ans;
        }
        
        private void helper(List<String> ans, String path, int start, int times, String s) {
            if (times == 4) {
                if (start == s.length()) {
                    ans.add(path.substring(0, path.length() - 1));
                }
                return;
            }
            
            for (int i = start + 1; i <= s.length(); ++i) {
                String sub = s.substring(start, i);
                if (sub.length() >= 2 && sub.charAt(0) == '0') {
                    break;
                }
                int number = Integer.parseInt(sub);
                if (number >= 0 && number <= 255) {
                    helper(ans, path + sub + ".", i, times + 1, s);
                } else {
                    break;
                }
            }
        }
    }

Log in to reply
 

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