93.複原IP位址

題解

• 當周遊到了字元串末尾，操作完成。
• 當ip位址的四段都已确定，而字元串還未周遊完，操作完成。
• 當下一字元為0，後一段ip隻能為單一的0。
• 當選擇的數超過255，for循環中必須break。

class Solution {
    List<String> res = new LinkedList<>();  // 結果
    public List<String> restoreIpAddresses(String s) {
        int[] segments = new int[4];
        backtrack(s, 0, 0, segments);
        return res;
    }

    public void backtrack(String s, int start, int segmentNum, int[] segments) {
        // 到達結束條件
        if (segmentNum == 4) {
            if (start == s.length()) {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < 3; i++) {
                    sb.append(segments[i]).append(".");
                }
                sb.append(segments[3]);
                res.add(sb.toString());
            }
            return;
        }

        // 提前回溯
        if (start == s.length()) {
            return;
        }

        // 限制條件，0開頭，特别處理
        if (s.charAt(start) == '0') {
            segments[segmentNum] = 0;
            backtrack(s, start + 1, segmentNum + 1, segments);
        }

        int temp = 0;
        for (int end = start; end < s.length(); end++) {
            // 做選擇
            temp = temp * 10 + (s.charAt(end) - '0');
            if (temp > 0 && temp <= 255) {
                segments[segmentNum] = temp;
                backtrack(s, end + 1, segmentNum + 1, segments);
            } else {    // 這個break極為重要，沒有的話會産生錯誤答案
                break;
            }
        }
    }
}