Restore IP Addresses -- LeetCode

 
這道題的解法非常接近於NP問題，也是采用遞歸的解法。基本思路就是取出一個合法的數字，作為IP地址的一項，然後遞歸處理剩下的項。可以想象出一顆樹，每個結點有三個可能的分支（因為范圍是0-255，所以可以由一位兩位或者三位組成）。並且這裡樹的層數不會超過四層，因為IP地址由四段組成，到了之後我們就沒必要再遞歸下去，可以結束了。這裡除了上述的結束條件外，另一個就是字符串讀完了。可以看出這棵樹的規模是固定的，不會像平常的NP問題那樣，時間復雜度取決於輸入的規模，是指數量級的，所以這道題並不是NP問題，因為他的分支是四段，有限制。代碼如下：

public ArrayList restoreIpAddresses(String s) {
    ArrayList res = new ArrayList();
    if(s==null || s.length()==0)
        return res;
    helper(s,0,1,,res);
    return res;
}
private void helper(String s, int index, int segment, String item, ArrayList res)
{
    if(index>=s.length())
        return;
    if(segment == 4)
    {
        String str = s.substring(index);
        if(isValid(str))
        {
            res.add(item+.+str);
        }
        return;
    }
    for(int i=1;i<4&&(i+index<=s.length());i++)
    {
        String str = s.substring(index, index+i);
        if(isValid(str))
        {
            if(segment==1)
                helper(s,index+i,segment+1,str,res);
            else
                helper(s,index+i,segment+1,item+.+str,res);
        }
    }
}
private boolean isValid(String str)
{
    if(str==null || str.length()>3)
        return false;
    int num = Integer.parseInt(str);
    if(str.charAt(0)=='0' && str.length()>1)
        return false;
    if(num>=0 && num<=255)
        return true;
    return false;
}