题解 | #74.数字字符串转化成IP地址#

递归+回溯

终止条件 count==4 && str==""时返回

注意00、010、023这样的地址是非法的，碰见这种情况直接return

 function restoreIpAddresses( s ) {
  let ans = [];
  let path = [];
   
  function traceTrack(str,count){
    if(count==4){
      if(str=="")
        ans.push(path.join('.'));
      return;
    }
    
    for(let i=1; i<=3 && i<=str.length; i++){
      if( parseInt( str.substring(0,i) ) <= 255  ){
        if(i>=2 && str[0]=='0' && str[1]=='0')//防止00出现
          return;
        if(i>=2  && str[0]=='0' && str[1]!='0')//防止010这样的出现
          return;
        path.push(str.substring(0,i));
        traceTrack(str.substring(i,str.length),count+1);
        path.pop();
      }
    }
  }
  traceTrack(s,0)
  return ans;
}
module.exports = {
    restoreIpAddresses : restoreIpAddresses
};