使用遞回函式列出給定字串中所有可能的IP地址組合

我有一個 String s = "25525511135"。如何使用遞回函式找到所有可能的 IP 地址串列。我為此目的撰寫了一個遞回函式，但它不起作用。我不明白的地方，我犯了一個錯誤。

String s = "25525511135";
int endInd = 1,strInd = 1;
String strNum = s.substring(0,1);

public void restoreIp(String s,List<List<String>> results,List<String> combination,
                          int startIndex, int endIndex,String strNum){

        int num = Integer.parseInt(strNum);
        Integer sumStr = combination.stream().mapToInt(String::length).reduce(0,Integer::sum);

        if (sumStr == s.length() && combination.size() == 4){
            results.add(new ArrayList<>(combination));
            return;
        }

        for (int i = startIndex; i < s.length(); i  ){

            if (num >= 0 && num <= 255 && combination.size() < 4){
                combination.add(""   num);
            } else { break; }

            if (sumStr < s.length() && combination.size() > 4){ break; }

            if (sumStr < s.length() && combination.size() == 4){
                if (endIndex < 4) {
                    endIndex = endIndex   1;
                } else {
                    break;
                }
            }

            restoreIp(s,results,combination,i 1,endIndex,s.substring(i,startIndex   endIndex));
            combination.remove(combination.size() - 1);
        }

    }

我需要在results串列中收集所有可能的串列。結果應如下所示：

[
[255,255,11,135]]
[255,255,111,35]
]

uj5u.com熱心網友回復：

這個問題的解決方法如下：

我們的函式只需要四個引數，要決議的字串、結果串列、當前找到的組合以及從何處開始形成新 IP 地址的索引。

public void restoreIp(String s, List<List<Integer>> results, List<Integer> combination, int startIndex)

我們首先宣告停止條件，當組合有 4 個數字或字串被完全決議時，我們停止呼叫函式。如果組合有 4 個數字并且字串被完全決議，我們將組合添加到結果串列中，否則我們將中斷遞回呼叫。

if (combination.size() == 4 && startIndex >= s.length()) {
    results.add(combination);
    return;
}

if (combination.size() == 4 || startIndex >= s.length()) {
    return;
}

現在演算法的主體是從startIndex開始遍歷字串并開始形成新數字，如果數字以 0 開頭并且有兩個以上的數字（01、02 等）或大于 255，我們將停止迭代因為不是有效的IP號碼，否則我們添加的數量組合和函式呼叫自身。

for (int i = startIndex; i < s.length(); i  ) {
    String strNumber = s.substring(startIndex, i   1);
    int number = Integer.parseInt(strNumber);
    if ((s.charAt(startIndex) == '0' && strNumber.length() > 1) || number > 255) {
        return;
    }
    List<Integer> newCombination = new ArrayList<>(combination);
    newCombination.add(number);

    restoreIp(s, results, newCombination, i   1);
}

所以整個代碼是：

public static void restoreIp(String s, List<List<Integer>> results, List<Integer> combination, int startIndex) {
    if (combination.size() == 4 && startIndex >= s.length()) {
        results.add(combination);
        return;
    }
    
    if (combination.size() == 4 || startIndex >= s.length()) {
        return;
    }
    
    for (int i = startIndex; i < s.length(); i  ) {
        String strNumber = s.substring(startIndex, i   1);
        int number = Integer.parseInt(strNumber);
        if ((s.charAt(startIndex) == '0' && strNumber.length() > 1) || number > 255) {
            return;
        }
        List<Integer> newCombination = new ArrayList<>(combination);
        newCombination.add(number);
    
        restoreIp(s, results, newCombination, i   1);
    }
}

測驗：

String str = "17125120120";
List<List<Integer>> result = new ArrayList<>();
restoreIp(str, result, new ArrayList<>(), 0);
System.out.println(result);

將產生：

[[17, 125, 120, 120], [171, 25, 120, 120], [171, 251, 20, 120], [171, 251, 201, 20]]

與： s = "25525511135"

[[255, 255, 11, 135], [255, 255, 111, 35]]

標籤：爪哇 递归

上一篇：如何鍵入遞回可變引數元組

下一篇：不理解C中的遞回函式