对于递归的迷惑

求助各位编程大牛， 我做leetcode的题“Restore IP addresses” http://oj.leetcode.com/problems/restore-ip-addresses/, 对于递归的应用非常迷茫， 求助。
一下为我尝试理解的答案。

package algorithm.sort;

public class RestoreIPAddress {

        /**

         *  

         * Restore IP Addresses

         *  

         *  

         * Given a string containing only digits, restore it by returning all possible valid IP address combinations.

         

        For example:

        Given "25525511135",

         

        return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

         *

         */  

       

          

            public static void main(String args[]) {  

                System.out.println(restoreIpAddresses("25525511135"));  

            }  

          

            public static ArrayList<String> restoreIpAddresses(String s) {  

                ArrayList<String> al = new ArrayList<String>();  

                if(s.length() > 12){     // 及时过滤  

                    return al;  

                }  

                StringBuilder sb = new StringBuilder();  

                dfs(s, al, sb, 0);  

                return al;  

            }  

             

            public static boolean isValid(String s){  

                if(s.length()==0 || s.length()>3){  

                    return false;  

                }  

                int val = Integer.parseInt(s);  

                if(!String.valueOf(val).equals(s)){     // 防止解析成00.01.010.0类似的情况  

                    return false;  

                }  

                if(val<0 || val>255){  

                    return false;  

                }  

                return true;  

            }  

             

            public static void dfs(String s, ArrayList<String> al, StringBuilder sb, int level){  

                if(level == 3){     // 第3次特别判断，必须取剩下的全部字符串  

                    if(isValid(s)){  

                        sb.append(s);  

                        al.add(sb.toString());      // 最后一次不加.  

                        sb.delete(sb.length()-s.length(), sb.length()); // 撤销动作  

                        return;  

                    }  

                }  

                  

                for(int i=0; i<s.length()-1; i++){  

                    String substr = s.substring(0, i+1);  

                    if(isValid(substr)){  

                        sb.append(substr).append(".");      // 执行动作  

                        dfs(s.substring(i+1), al, sb, level+1);      

                        sb.delete(sb.length()-1-substr.length(), sb.length());  // 撤销动作  

                    }  

                }  

            }  

        }  

你这个代码太长了。不利于你理解算法的本质。
不知道楼主会不会python
我这题用python做过。
https://github.com/Linzertorte/L ... storeIPAddresses.py

Linzertorte 发表于 2014-4-4 13:16
你这个代码太长了。不利于你理解算法的本质。
不知道楼主会不会python
我这题用python做过。

万分感谢，我研究研究， 感谢感谢

没细看楼主的代码，我觉得至少最后一个循环，可以写成1-3的循环，而不是0到s.length()-1。

用笨方法写了个代码，如下：

1. 
   

复制代码

搞了好几次，代码也没黏进去。可能改的次数太多了，上面那个帖子已经不能编辑了。代码如下：


public class Solution {
        public static void main(String args[]) {
               
                int[] len = new int[4];
               
                String ipStr = "25525511135";
               
                int lenIpStr = ipStr.length();
               
                for (len[0]=1; len[0]<=3; len[0]++) {
                        for (len[1]=1; len[1]<=3; len[1]++) {
                                for (len[2]=1; len[2]<=3; len[2]++) {
                                        for (len[3]=1; len[3]<=3; len[3]++) {
                                                if (len[0] + len[1] + len[2] + len[3] == lenIpStr) {
                                                        int start = 0;
                                                        int end = 0;
                                                        int i;
                                                        String[] ip = new String[4];
                                                        for (i=0; i<4; i++) {
                                                                end += len[i];
                                                                ip[i] = ipStr.substring(start, end);
                                                                if (! isValid(ip[i])) {break;}
                                                                start = end;
                                                        }
                                                if (i==4) {
                                                        System.out.println("[" + ip[0] + "." + ip[1] + "." + ip[2] + "." + ip[3] + "]" );
                                                }
                                                }
                                        }
                                }
                        }
                }

        }
       
       
    public static boolean isValid(String s){  
        int val = Integer.parseInt(s);  
        if(!String.valueOf(val).equals(s)){     // 防止解析成00.01.010.0类似的情况  
            return false;  
        }  
        if(val<0 || val>255){  
            return false;  
        }  
        return true;  
    }  
}