Share my clean dfs Java code


  • 3
    M
    /*
        dfs. 在每一层, 取字符串的前1/2/3个字母
        第四层时检查并collect answer.
    */
    public class Solution {
        public List<String> restoreIpAddresses(String s) {
             List<String> ans = new ArrayList<>();
             dfs(ans, new StringBuilder(), s, 0);
             return ans;
        }
        
        private void dfs(List<String> ans, StringBuilder cur, String s, int level) {
            if (level == 4) {  // all previous 4 segments are done
                if (s.length() == 0) {  // s is entirely used
                    ans.add(cur.toString().substring(0, cur.length() - 1));  // remove the dot at tail
                }
                return;
            }
            for (int i = 1; i <= Math.min(3, s.length()); ++i) {  // length of each segment are at most 3
                String curPart = s.substring(0, i);
                if (curPart.length() > 1 && curPart.charAt(0) == '0' || Integer.parseInt(curPart) > 255) {
                    break;
                }
                cur.append(curPart).append(".");
                dfs(ans, cur, s.substring(i), level + 1);
                cur.delete(cur.length() - curPart.length() - 1, cur.length());
            }
        }
    }

Log in to reply
 

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