一、題目描述
有效 IP 地址 正好由四個整數（每個整數位于 0 到 255 之間組成，且不能含有前導 0），整數之間用 '.' 分隔。
- 例如：
"0.1.2.201"和"192.168.1.1"是 有效 IP 地址，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是 無效 IP 地址。
給定一個只包含數字的字符串 s ，用以表示一個 IP 地址，返回所有可能的有效 IP 地址，這些地址可以通過在 s 中插入?'.' 來形成。你 不能?重新排序或刪除 s 中的任何數字。你可以按 任何 順序返回答案。
示例 1：
輸入：s = "25525511135" 輸出：["255.255.11.135","255.255.111.35"]
示例 2：
輸入：s = "0000" 輸出：["0.0.0.0"]
示例 3：
輸入：s = "101023" 輸出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
提示：
1 <= s.length <= 20s僅由數字組成
二、解題思路
這個問題是一個典型的回溯問題，我們可以使用遞歸的方式來解決。首先，我們需要明確幾個規則：
- IP 地址由四部分組成，每部分的范圍在 0 到 255 之間。
- 每部分可以是 1 到 3 位數字。
- 不能有前導 0，即 0 不能出現在除了單個 0 自身以外的其他數字的開頭。
基于以上規則，我們可以按照以下步驟來解決這個問題：
- 初始化一個列表?
result?來保存所有可能的 IP 地址。 - 定義一個遞歸函數?
restoreIpAddressesHelper，該函數接受當前構建的 IP 地址?currentIp，剩余未處理的字符串?remaining，以及當前已添加的段數?segment。 - 在遞歸函數中，如果?
segment?等于 4 且?remaining?為空，說明一個有效的 IP 地址構建完成，將其添加到?result?列表中。 - 遍歷?
remaining?字符串，對于每個位置，嘗試提取 1 到 3 位數字作為 IP 地址的一部分，并遞歸調用?restoreIpAddressesHelper。 - 在遞歸調用之前，檢查提取的數字是否在 0 到 255 的范圍內，且沒有前導 0（除了數字 0 本身）。
- 最后，返回?
result?列表。
三、具體代碼
import java.util.ArrayList;
import java.util.List;public class Solution {public List<String> restoreIpAddresses(String s) {List<String> result = new ArrayList<>();restoreIpAddressesHelper(result, "", s, 0);return result;}private void restoreIpAddressesHelper(List<String> result, String currentIp, String remaining, int segment) {if (segment == 4 && remaining.isEmpty()) {result.add(currentIp);return;}for (int i = 1; i <= 3 && i <= remaining.length(); i++) {String part = remaining.substring(0, i);if ((part.startsWith("0") && part.length() > 1) || Integer.parseInt(part) > 255) {continue;}restoreIpAddressesHelper(result, currentIp.isEmpty() ? part : currentIp + "." + part, remaining.substring(i), segment + 1);}}public static void main(String[] args) {Solution solution = new Solution();List<String> ipAddresses = solution.restoreIpAddresses("25525511135");System.out.println(ipAddresses);}
}
四、時間復雜度和空間復雜度
1. 時間復雜度
-
最壞情況分析：對于 IP 地址的每個部分，我們有三種選擇：取一位、取兩位或取三位數字。因此，對于四個部分，最壞情況下的時間復雜度是 O(3^4)。
-
實際分析：然而，由于輸入字符串?
s?的長度限制（1 <= s.length <= 20），我們通常不會探索所有可能的選擇。例如，如果剩余的字符串長度不足以構成四個有效的 IP 地址部分，我們會提前停止遞歸。這意味著實際的時間復雜度會低于 O(3^4)。 -
遞歸調用次數：遞歸調用的次數取決于輸入字符串的長度和字符串中數字的分布。在最壞情況下，每次遞歸調用會有三次新的遞歸調用，但這通常會被輸入字符串的長度限制所減少。
-
綜上所述，時間復雜度是 O(3^4)，但通常會低于這個值。
2. 空間復雜度
-
遞歸棧空間：遞歸棧的最大深度是 4，因為 IP 地址有四部分。因此，遞歸棧的空間復雜度是 O(4)。
-
結果存儲空間：結果列表?
result?的大小取決于輸入字符串?s?可以形成的有效 IP 地址的數量。在最壞情況下，這個數量是 O(3^4)。然而，實際上，由于輸入字符串的長度限制，生成的有效 IP 地址數量通常會遠小于這個上界。 -
實際空間復雜度：由于實際的 IP 地址數量通常遠小于 O(3^4)，實際的空間復雜度通常會低于這個值。
-
綜上所述，空間復雜度是 O(3^4)，但通常會低于這個值。
五、總結知識點
-
回溯算法：這是一種通過探索所有可能的候選解來找到所有解的算法。如果候選解被確認不是一個解（或者至少不是最后一個解），回溯算法會丟棄該解，即回溯并且嘗試另一個候選解。
-
遞歸：這是一種編程技巧，函數自己調用自己。在這個問題中，
restoreIpAddressesHelper?函數遞歸地調用自己來探索所有可能的 IP 地址組合。 -
字符串操作：代碼中使用了字符串的?
substring?方法來提取字符串的一部分，以及?isEmpty?和?startsWith?方法來檢查字符串是否為空或者是否以某個特定字符開頭。 -
整數轉換：使用了?
Integer.parseInt?方法將字符串轉換為整數。這在檢查提取的字符串是否在 0 到 255 的范圍內時使用。 -
列表（List）：使用了?
ArrayList?來存儲找到的所有可能的 IP 地址。ArrayList?是 Java 中 List 接口的一個實現，它允許我們動態地添加、刪除和訪問元素。 -
條件語句：使用了?
if?語句來檢查遞歸的基本情況（當生成了一個完整的 IP 地址時）以及提取的字符串部分是否有效。 -
循環：使用了?
for?循環來遍歷所有可能的字符串部分長度（1 到 3）。 -
函數定義和調用：定義了?
restoreIpAddresses?和?restoreIpAddressesHelper?兩個函數，并在?restoreIpAddresses?函數中調用了?restoreIpAddressesHelper。 -
參數傳遞：在遞歸調用中，通過參數傳遞當前的 IP 地址部分、剩余的字符串和當前段數。
-
遞歸的基本情況：在?
restoreIpAddressesHelper?函數中，當生成了一個完整的 IP 地址時（段數為 4 且沒有剩余的字符串），將其添加到結果列表中，這是遞歸的基本情況。 -
遞歸的遞推關系：在?
restoreIpAddressesHelper?函數中，通過遞歸調用自己來處理下一個 IP 地址段，這是遞歸的遞推關系。
以上就是解決這個問題的詳細步驟，希望能夠為各位提供啟發和幫助。
