[LeetCode]Restore IP Addresses, 解題報告

前言

好久沒有寫關於ACM的博客了，確實是最近太忙，也怪我之前涉獵太少，一個簡單的app花費了將近兩個月的精力，還是沒有很好的完成，慚愧！
清明假期三天，一天和女朋友一起出去吃了個飯打打乒乓球，一天憋出了大論文的8000字，剩今天最後一天就拿來補覺加寫寫ACM。
對於ACM，我認為工作中能用到的可能性比較小，但是不代表它沒用，然後我對ACM純屬個人興趣，但是2個月沒碰過算法寫起來也不是那麼順手了，今天隨便記錄一個DFS的問題。

題目

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)

思路

首先，IP地址分為4部分，每部分的數字合法范圍是0-255
其次，對於一串給定的字符串，我們每次可以取一個、兩個、或者三個字符組成字符串。如果沒有越界並且字符串滿足0-255的要求，則保留該部分並對剩下的字符串進行DFS搜索，直到組成四個部分為止。如果越界或者不合要求，直接跳過即可。

AC代碼

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

        StringBuilder tmp = new StringBuilder();

        depthFS(0, 0, s, tmp, res);

        return res;
    }

    public static void depthFS(int count, int index, String s, StringBuilder tmp,
            ArrayList res) {
        if (count == 4 && index == s.length()) {
            res.add(tmp.toString().substring(0, tmp.length() - 1));
            return;
        } else {
            for (int i = 1; i <= 3 && index + i <= s.length(); i++) {
                String tmpStr = s.substring(index, index + i);
                if (isValid(tmpStr)) {
                    int bt = tmp.length();
                    int ed = tmp.length() + tmpStr.length();
                    tmp.append(tmpStr).append(".");
                    depthFS(count + 1, index + i, s, tmp, res);
                    tmp.delete(bt, ed + 1);
                }
            }
        }
    }

    public static boolean isValid(String s) {
        if (s.charAt(0) == '0') {
            return s.equals("0");
        }

        int num = Integer.parseInt(s);

        return num > 0 && num <= 255;
    }
}