在 Java 中根據給定的數字字串產生所有可能的 IP 位址
1. 概述
在本教程中，我們將探索在 Java 中從給定數字字串生成所有可能的 IP 位址的不同方法。這個問題是常見的面試問題。我們將首先深入研究問題陳述，然後介紹幾種解決問題的技術，包括暴力破解、回溯和動態程式設計。
2. 理解問題陳述
我們給定一個僅包含數字的字串S ，目標是找到並傳回所有可能的有效 IP 位址，這些位址可以透過在S中插入點來形成。我們無法刪除或重新排序任何數字；結果可以按任何順序返回。
例如，對於給定的字串“101024”,我們將得到以下輸出：
["1.0.10.24","1.0.102.4","10.1.0.24","10.10.2.4","101.0.2.4"]上面的輸出列出了給定字串可以形成的所有有效 IP 位址。有效的 IPv4 位址由四個用點分隔的八位元組組成。每個八位元組都是 0 到 255 之間的數字。
0.0.0.0
192.168.0.8
234.223.43.42
255.255.255.03. 迭代方法
在這種方法中，我們將使用三個嵌套循環來迭代可能的位置，以將字串分成四個部分。外循環遍歷第一部分，中循環遍歷第二部分，內循環遍歷第三部分。我們將把字串的剩餘部分視為第四段。
獲得分段組合後，我們將提取子字串並使用isValid()方法驗證每個分段以確定它是否構成 IP 位址的有效部分。 isValid()方法負責檢查給定字串是否是 IP 位址的有效部分。它確保整數值在 0 到 255 之間並且沒有前導零：
public List<String> restoreIPAddresses(String s) {
List<String> result = new ArrayList<>();
if (s.length() < 4 || s.length() > 12) {
return result;
}
for (int i = 1; i < 4; i++) {
for (int j = i + 1; j < Math.min(i + 4, s.length()); j++) {
for (int k = j + 1; k < Math.min(j + 4, s.length()); k++) {
String part1 = s.substring(0, i);
String part2 = s.substring(i, j);
String part3 = s.substring(j, k);
String part4 = s.substring(k);
if (isValid(part1) && isValid(part2) && isValid(part3) && isValid(part4)) {
result.add(part1 + "." + part2 + "." + part3 + "." + part4);
}
}
}
}
return result;
}
private boolean isValid(String part) {
if (part.length() > 1 && part.startsWith("0")) { return false; }
int num = Integer.parseInt(part);
return num >= 0 && num <= 255;
}方法restoreIPAddresses()產生並傳回所有可能的有效IP 位址。它還檢查字串長度是否超出 4 到 12 個字元的範圍，如果超出則傳回一個空列表，因為在這種情況下無法形成有效的 IP 位址。
我們使用巢狀循環來迭代三個點的所有可能位置。這將時間複雜度增加到O(n 2 ) 。它不是O(n 3 ) ，因為外循環有固定的迭代次數。此外，我們在每次迭代期間建立臨時子字串，這將整體空間複雜度增加到O(n) 。
4. 回溯法
回溯時，我們透過將字串分成四部分來產生所有可能的 IP 位址。在每個步驟中，我們使用相同的isValid()方法執行驗證，以檢查字串是否非空且沒有前導零。如果它是有效的字串，我們將進入下一部分。一旦我們完成了所有四個部分並使用了所有字符，我們將它們添加到結果列表中：
public List<String> restoreIPAddresses(String s) {
List<String> result = new ArrayList<>();
backtrack(result, s, new ArrayList<>(), 0);
return result;
}
private void backtrack(List<String> result, String s, List<String> current, int index) {
if (current.size() == 4) {
if (index == s.length()) {
result.add(String.join(".", current));
}
return;
}
for (int len = 1; len <= 3; len++) {
if (index + len > s.length()) { break;
}
String part = s.substring(index, index + len);
if (isValid(part)) {
current.add(part);
backtrack(result, s, current, index + len);
current.remove(current.size() - 1);
}
}
}backtrack函數將字串分成 4 個整數段，每個段最多 3 位數字。這導致了 3 4 種可能的分割字串的方式。評估每個段落是否有效需要O(1)時間，因為它涉及檢查段的長度和範圍。由於可能的配置數量 3 4是恆定的並且不依賴輸入字串長度，因此時間複雜度簡化為O(1) 。
遞歸深度限制為 4，因為 IP 位址中正好有 4 個段。因此，由於配置數量和所需空間是常數，因此空間複雜度簡化為O(1) 。
5.動態規劃方法
動態規劃是一種流行的演算法範例，它使用循環公式來尋找解決方案。它類似於分治策略，因為它將問題分解為更小的子問題。其解決方案使用數組來儲存先前計算值的結果。
現在，我們將使用dp陣列來儲存所有有效的 IP 前綴。我們先初始化一個 2D 列表dp其中dp[i][j]儲存所有可能的 IP 位址段，直到第i個字元和j個段。之後，我們檢查所有可能的段長度（1 到 3）並使用isValid()方法驗證每個段落。如果一個段落有效，我們會將其附加到先前狀態的前綴中。我們在dp[n][4].
public List<String> restoreIPAddresses(String s) {
int n = s.length();
if (n < 4 || n > 12) { return new ArrayList<>();
}
List<String>[][] dp = new ArrayList[n + 1][5];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= 4; j++) {
dp[i][j] = new ArrayList<>();
}
}
dp[0][0].add("");
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= 4; k++) {
for (int j = 1; j <= 3 && i - j >= 0; j++) {
String segment = s.substring(i - j, i);
if (isValid(segment)) {
for (String prefix : dp[i - j][k - 1]) {
dp[i][k].add(prefix.isEmpty() ? segment : prefix + "." + segment);
}
}
}
}
}
return dp[n][4];
}dp數組的初始化需要O(n*4)時間，簡化為O(n).負責填入dp表的巢狀迴圈需要O(n*4*3)時間，簡化為O(n).空間複雜度也是O(n*4)簡化為O(n) 。
六、結論
在本文中，我們討論了從給定的數字字串生成所有可能的 IP 位址組合，並了解了解決該問題的各種方法。迭代方法很簡單，但時間複雜度很高O(n 2 ) 。為了獲得更好的效能，我們可以使用動態程式方法，該方法提供更好的O(n)時間複雜度。
回溯程式設計方法被證明是最有效的一種，因為它在我們討論的所有其他方法中具有最佳的運行時間O(1) 。
與往常一樣，本文中使用的程式碼可以在 GitHub 上找到。