my backtracking answer in java


  • 0
    M

    public class Solution {
    List<String> res;
    public List<String> restoreIpAddresses(String s) {
    res = new ArrayList<String>();
    if ( s.length() < 4 || s.length() > 12 ) {
    return res;
    }

        backTrack(new StringBuilder(), s, 0, 0);
        return res;
    }
    
    private void backTrack(StringBuilder str, String s, int start, int count) {
        if ( count == 4 && str.length() == s.length() + 3 ) {
            res.add(str.toString());
            return;
        }
        
        for ( int i = 1; i <= 3 && start + i <= s.length() ; i++ ) {
            if ( count == 3 && start + i != s.length() ) {
                continue;
            }
            String cut = s.substring(start, start + i);
            if ( isValid(cut) ) {
                StringBuilder newStr = new StringBuilder(str.toString());
                if ( count != 0 ) {
                    newStr.append(".");
                }
                newStr.append(cut);
                backTrack(newStr, s, start + i, count + 1);
            }
        }
    }
    
    private boolean isValid(String s) {
        if ( s.length() == 0 || (s.charAt(0)=='0' && s.length()>1) || Integer.parseInt(s) > 255 ) {
            return false;
        } 
        
        return true;
    }
    

    }


Log in to reply
 

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