93. Restore IP Addresses

dfs

class Solution {
    public List<String> restoreIpAddresses(String s) {
        // dfs
        List<String> result = new LinkedList<>();
        searchIp(s, "", result, 1, 0);
        return result;
    }
    
    private void searchIp(String s, String ip, List<String> result, int sectionCount, int start){
        if(sectionCount == 5){
            if(start>=s.length()) result.add(ip.substring(1, ip.length()));
            return;
        }
        
        for(int i = 1; i<=Math.min(4, s.length()-start); i++){
            if(!(i>1 && s.charAt(start)=='0')){
                String str = s.substring(start, start+i);
                // method: int Integer.valueOf(String)
                if (Integer.valueOf(str)<256){
                    // remember: ip+'.'+str generate a new string obj
                    searchIp(s, ip+'.'+str, result, sectionCount+1, start+i);
                }
            }
        }
    }
}