Short Java recursive solution with condition outside of loop. Beat 88%


  • 2

    Check if there are too many digits left or not enough left for remaining ip:

    if (s.length() > k * 3 || s.length() < k) 
    

    Check edge case "0":

    int maxLen = s.startsWith("0") ? maxLen = 1 : Math.min(s.length(), 3);
    
    public class Solution {
        public List<String> restoreIpAddresses(String s) {
            List<String> res = new ArrayList<>();
            search(4, "", s, res);
            
            return res;
        }
        
        private void search(int k, String ip, String s, List<String> res) {
            if (s.length() > k * 3 || s.length() < k) {
                return;
            }
            if (k == 0) {
                res.add(ip.substring(0, ip.length() - 1));
                return;
            }
            
            int maxLen = s.startsWith("0") ? maxLen = 1 : Math.min(s.length(), 3);
            
            for (int len = 1; len <= maxLen; len++) {
                if (Integer.parseInt(s.substring(0, len)) > 255) {
                    continue;
                }
                search(k - 1, ip + s.substring(0, len) + ".", s.substring(len), res);
            }
        }
    }
    

Log in to reply
 

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