Beats 98%! 2ms Java recursive solution.


  • 0
    E
    public class Solution {
        private List<String> rlist;
        
        public List<String> restoreIpAddresses(String s) {
            int len = s.length();
            rlist = new ArrayList<String>();
            char[] c = s.toCharArray();
            go(c, 0, len, 4, ""); //recursively
            return rlist;
        }
        
        private void go(char[] c, int i, int l, int k, String curstr){
            //i+l = c.length, i is current position of array c;
            if(k == 0 && l == 0) rlist.add(curstr.substring(1)); //the initial char is '.'
            if(k == 0 || l == 0) return;
            if(l > k * 3 || l < k) return;
            
            int p1 = c[i]-'0';
            go(c, i+1, l-1, k-1, curstr+"."+p1);
            
            if(l < 2 || c[i] == '0') return; //pay attention to those starting with '0'
            int p2 = (c[i]-'0') * 10 + c[i+1]-'0';
            go(c, i+2, l-2, k-1, curstr+"."+p2);
            
            if(l < 3) return;
            int p3 = (c[i]-'0') * 100 + (c[i+1]-'0') * 10 + c[i+2]-'0';
            if(p3 <=255) go(c, i+3, l-3, k-1, curstr+"."+p3);
            
            return;
        }
    }
    

Log in to reply
 

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