leetcode - [93] Restore IP Addresses

2020/06/22

问题描述

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

A valid IP address consists of exactly four integers (each integer is between 0 and 255) separated by single points.

给你一个仅包含数字的字符串,返回所有有效的IP地址组合。

有效IP地址的定义:仅包含四个整数,范围为0-255,并以分离。

举个例子:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

解法1

Thanks @greatgrahambini

整理下解题思路:

首先,我们的目标是什么?

将原始字符串分为四个有效的整数部分,并找到所有这样的组合。

所以,我们需要一个section变量,代表原始字符串已经被分成了几个部分。

section == 4,并且原始字符串遍历完后,说明什么?

我们找到了其中一个答案。

// Goal
if (section == 4 && start == s.length()){
    ans.add(new String(sb));
    return;
}

然后,我们来讲下递归函数中的循环。

局部变量i的初始值是01还是start?为什么?

让我们来明确一下start变量的作用是什么?

用于确定每次递归[每个section]的子字符串的起始位置。

至于子字符串的长度,则是由变量i决定的。

为了便于对字符串进行substring(),因此我们选择i的初始值为1

for (int i = 1; i <= 3; i++){
    ...  
}

接着,循环内部需要实现哪些功能?

第一步,需要获取当前section中的子字符串:

String sub = s.substring(start, start + i);

注意喔,为了防止索引溢出,需要校验start + i的长度。

// Check boundary.
if (start + i > s.length()) break;

第二步,就是校验子字符串。

  • 是否为0开头的数字?如: 020
  • 是否大于255
if (sub.startsWith("0") && sub.length() > 1) break;
if (Integer.parseInt(sub) > 255) break;

第三步,就是拼接可能的子结果,并进行递归,最后删除上层的拼接。

sb = section == 3 ? sb.append(sub) : sb.append(sub).append(".");
// Be careful: start + i;
bt(s, ans, sb, start + i, section + 1);
sb.delete(len, sb.length());

来看下完整实现:

class Solution {
    public List<String> restoreIpAddresses(String s) {
        
        List<String> ans = new LinkedList<>();
        if (s.length() == 0) return ans;
        bt(s, ans, new StringBuilder(), 0, 0);
        return ans;
    }
    
    private void bt(String s, List<String> ans, StringBuilder sb, int start, int section){
        
        // Early break.
        if (section > 4) return;
        
        // Goal
        if (section == 4 && start == s.length()){
            ans.add(new String(sb));
            return;
        }
        
        int len = sb.length();
        // Choice
        // The initialize of i is 1, which is for substring().
        for (int i = 1; i <= 3; i++){
            // Check boundary.
            if (start + i > s.length()) break;
            // Get and check substring.
            String sub = s.substring(start, start + i);
            if (sub.startsWith("0") && sub.length() > 1) break;
            if (Integer.parseInt(sub) > 255) break;
            sb = section == 3 ? sb.append(sub) : sb.append(sub).append(".");
            // Be careful: start + i;
            bt(s, ans, sb, start + i, section + 1);
            sb.delete(len, sb.length());
        }
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory