93. Restore IP Addresses

题目链接

https://leetcode.com/problems/restore-ip-addresses/

思路

三层for循环或者dfs

代码

class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> ans = new ArrayList<>();
            dfs(ans, s, "", 0, 3);
            return ans;
        }

        private void dfs(List<String> ans, String s, String t, int pos, int cnt) {
            if (cnt == 0) {
                if (s.length() - pos > 3) {
                    return;
                }
                String sub = s.substring(pos);
                if (match(sub)) {
                    ans.add(t + sub);
                }
                return;
            }
            int ed = Math.min(s.length() - 1, pos + 3);
            for (int i = pos + 1; i <= ed; i++) {
                String sub = s.substring(pos, i);
                if (match(sub)) {
                    dfs(ans, s, t + sub + ".", i, cnt - 1);
                }
            }
        }
        
        private boolean match(String s) {
            int it = Integer.parseInt(s);
            return it <= 255 && s.equals(String.valueOf(it));
        }
    }