NC20 数字字符串转化成IP地址

题目链接：https://www.nowcoder.com/practice/ce73540d47374dbe85b3125f57727e1e

题目描述

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

例如：

给出的字符串为"25525522135",

返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)

数据范围：字符串长度 0 ≤ n ≤ 12

要求：空间复杂度 O(n!),时间复杂度 O(n!)

注意：ip地址是由四段数字组成的数字序列，格式如 "x.x.x.x"，其中 x 的范围应当是 [0,255]。

示例 1：

输入："25525522135"
返回值：["255.255.22.135","255.255.221.35"]

示例 2：

输入："1111"
返回值：["1.1.1.1"]

示例 3：

输入："000256"
返回值："[]"

解题代码

import java.util.*;


public class Solution {
    /**
     * 
     * @param s string字符串 
     * @return string字符串ArrayList
     */
    //找切割点 和 层数
    ArrayList<String> res = new ArrayList<>();
    LinkedList<String> path = new LinkedList<>();
    public ArrayList<String> restoreIpAddresses (String s){
        // write code here
        if (s.length() == 0) {
            return res;
        }
        process(s, 0);
        return res;
    }
    public void process (String s,int start){
        if (path.size() > 4) {
            return;
        }
        if (path.size() == 4 && start == s.length()) {
            res.add(String.join(".", path));
            return;
        }
        for (int i = start; i < s.length(); i++) {
            String cur = s.substring(start, i + 1);
            if (!isValid(cur)) {
                continue;
            }
            path.add(cur);
            process(s, i + 1);
            path.removeLast();
        }
    }
    public boolean isValid (String cur){
        if (cur.charAt(0) == '0' && cur.length() > 1) {
            return false;
        }
        if (cur.length() > 3) {
            return false;
        }
        if (Integer.valueOf(cur) > 255) {
            return false;
        }
        return true;
    }
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请标明出处。
最后编辑时间为: 2022/08/18 19:19:52