这道题采用穷举法。

1  /** 2       * Given a string containing only digits, 3       *  restore it by returning all possible valid IP address combinations. 4       *  采用穷举法 5       * @param s 6       * @return 7       */ 8      public ArrayList
     
       restoreIpAddresses(String s) { 9          ArrayList
      
        r = new ArrayList
       
        ();10          int len = s.length();11          for(int i=1;i<=3;i++){12              for(int j = i+1; j<=i+3;j++){13                  for(int k = j+1;k<=j+3;k++){14                      if(k>len-1)15                          continue;16                      String A = s.substring(0,i);17                      String B = s.substring(i,j);18                      String C = s.substring(j,k);19                      String D = s.substring(k);20                      StringBuilder sb = new StringBuilder();21                      if(isValid(D) && isValid(C) && isValid(B) && isValid(A)){22                          sb.append(A).append(".").append(B).append(".").append(C).append(".").append(D);23                          r.add(sb.toString());24                      }25                  }26              }27          }28          return r;29      }30      /**31       * 用于验证IP地址某一部分是否是有效的32       * @param s33       * @return34       */35      private boolean isValid(String s){36          if(s.length()>3)37              return false;38          if(Integer.valueOf(s)>255)39              return false;40          int len = s.length();41          char[] cs = s.toCharArray();42          if(len>1 && cs[0] == '0' )43              return false;44          45          return true;46      }