《算法通关村——回溯模板如何解决回溯问题》

发布时间:2023年12月18日

《算法通关村——回溯模板如何解决回溯问题》

93. 复原 IP 地址

有效 IP 地址 正好由四个整数(每个整数位于 0255 之间组成,且不能含有前导 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 <= 20
  • s 仅由数字组成

题解

class Solution {
    List<String> result = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        if(s.length() < 4 || s.length() > 12){
            return result;
        }
        backTrace(s,0,0);
        return result;
    }
    // startIndex: 搜索的起始位置, pointNum: 添加小数点的数量
    private void backTrace(String s,int startIndex, int pointNum){
        if(pointNum == 3){
            // 小数点数量为3时结束分割
            // 判断第四段子字符串是否合法,如果合法就放进result中
            if (isValid(s,startIndex,s.length()-1)){
                result.add(s);
            }
            return;
        }
        for(int i = startIndex;i<s.length() ;i++){
            if(isValid(s,startIndex,i)){
                // 在 Str 的后面插入小数点
                s = s.substring(0,i+1) + "." +s.substring(i+1);
                pointNum++;
                // 插入小数点之后下一个字串的起始位置为 i + 2
                backTrace(s, i+2 ,pointNum);
                pointNum--;// 撤销操作
                s = s.substring(0,i+1) + s.substring(i+2);// 撤销操作
            }else{
                break;
            }
        }
    }
    private Boolean isValid(String s,int start , int end) {
        if (start > end){
            return false;
        }
        // 0开头的数字不合法
        if(s.charAt(start) == '0' && start != end){
            return false;
        }

        int num = 0;
        for(int i = start;i<=end;i++){
            //遇到非数字字符不合法
            if(s.charAt(i) > '9' || s.charAt(i) < '0'){
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0') ;
            if( num > 255) {
                return false;
            }
        }
        return true;
    }
}

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

在这里插入图片描述

示例 1:

输入:digits = "23"
输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2:

输入:digits = ""
输出:[]

示例 3:

输入:digits = "2"
输出:["a","b","c"]

提示:

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

题解

class Solution {
    List<String> list = new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0){
            return list;
        }
        // 初始对应所有的数字,为了直接对应 2 - 9,新增了两个无效的字符串
        String[] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        backTracking(digits,numString,0);
        return list;
    }
    // 每次迭代获取一个字符串,所以会涉及大量的字符嫔节,所以这里选择更为高效的 StringBuilder
    StringBuilder temp = new StringBuilder();

    // 比如digits如果为”23“,num=0,则str表示2的对应abc
    public void backTracking(String digits,String[] numString,int num){
        // 遍历全部一次记录一次得到的字符串
        if ( num == digits.length()){
            list.add(temp.toString());
            return ;
        }
        // str 表示当前num 对应的字符串
        String str = numString[digits.charAt(num) - '0'];
        for(int i = 0;i < str.length() ;i++){
            temp.append(str.charAt(i));
            backTracking(digits,numString,num+1);
            temp.deleteCharAt(temp.length() - 1);
        }
    }
}

22. 括号生成

数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。

示例 1:

输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]

示例 2:

输入:n = 1
输出:["()"]

提示:

  • 1 <= n <= 8

题解

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backTracking(ans,new StringBuilder(),0,0,n);
        return ans;
    }
    public void backTracking(List<String> ans,StringBuilder cur,int open,int close,int max) {
        if(cur.length() == max *2 ){
            ans.add(cur.toString());
            return ;
        }
        if(open < max){
            cur.append('(');
            backTracking(ans,cur,open+1,close,max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if(close < open ){
            cur.append(')');
            backTracking(ans,cur,open,close + 1,max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}
文章来源:https://blog.csdn.net/Go_ahead_forever/article/details/134948857
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。