Verkada

01Find Valid IP Addresses

You are given a root directory path and a representation of files in a file system. Each file is represented as [path, content], where path is the full path to the file and content is the file's text. Consider only files whose path lies under the given root directory. Scan those files recursively and collect every whitespace-separated token that is a valid IPv4 address. A token is a valid IPv4 address if it has exactly four decimal octets separated by dots, each octet is in the range 0 to 255, and no octet has a leading zero unless the octet is exactly 0. Return all valid IPv4 addresses found in the scanned files, sorted in lexicographic order. If the same valid address appears multiple times, keep each occurrence. Function Description Complete the function findValidIpAddresses in the editor below. findValidIpAddresses has the following parameters:

String rootPath: the directory whose descendant files should be scanned
String[][] files: each row is [path, content] Returns String[]: the valid IPv4 addresses discovered under rootPath, in lexicographic order.

Constraints

The source thread did not provide explicit numeric bounds.

Each row of files contains exactly two strings: the file path and the file content.
Only descendant files of rootPath are considered.
File contents are scanned as whitespace-separated tokens.

Example 1

Input:

rootPath = "/var/log"
files = [["/var/log/a.txt", "client 10.1.1.1 backup 256.1.1.1"], ["/var/log/sub/b.txt", "gateway 192.168.0.1 bad 01.2.3.4"], ["/tmp/ignore.txt", "8.8.8.8"]]

Output:

["10.1.1.1", "192.168.0.1"]

Explanation: Only files under /var/log are scanned. 10.1.1.1 and 192.168.0.1 are valid IPv4 addresses. 256.1.1.1 is invalid because 256 is out of range, and 01.2.3.4 is invalid because of the leading zero.

Example 2

Input:

rootPath = "/data"
files = [["/data/r1.txt", "hosts 1.1.1.1 0.0.0.0"], ["/data/archive/r2.txt", "bad 1.1.1 999.0.0.1 10.10.10.10"], ["/data/r3.txt", "repeat 1.1.1.1"]]

Output:

["0.0.0.0", "1.1.1.1", "1.1.1.1", "10.10.10.10"]

Explanation: All three files are descendants of /data. The valid IPv4 tokens are 1.1.1.1, 0.0.0.0, 10.10.10.10, and another 1.1.1.1. They are returned in lexicographic order, with duplicates preserved.

解法

过滤路径以 rootPath 加 / 起头(或恰等于 root 下文件)的文件；对每个文件，按空白拆分为 token，逐个用正则/手写校验是否为合法 IPv4：4 段、每段为十进制 0–255、不带前导零(除非本身就是 0)。收集并按字典序排序(重复保留)。时间 O(总字节)。

from typing import List

def find_valid_ip_addresses(root_path: str, files: List[List[str]]) -> List[str]:
    def valid(tok: str) -> bool:
        parts = tok.split(".")
        if len(parts) != 4:
            return False
        for p in parts:
            if not p.isdigit():
                return False
            if len(p) > 1 and p[0] == "0":
                return False
            if int(p) > 255:
                return False
        return True

    prefix = root_path.rstrip("/") + "/"
    out: List[str] = []
    for path, content in files:
        if not path.startswith(prefix):
            continue
        for tok in content.split():
            if valid(tok):
                out.append(tok)
    out.sort()
    return out

import java.util.*;

class Solution {
    public String[] findValidIpAddresses(String rootPath, String[][] files) {
        String prefix = rootPath.endsWith("/") ? rootPath : rootPath + "/";
        List<String> out = new ArrayList<>();
        for (String[] f : files) {
            if (!f[0].startsWith(prefix)) continue;
            for (String tok : f[1].split("\\s+")) {
                if (isValid(tok)) out.add(tok);
            }
        }
        Collections.sort(out);
        return out.toArray(new String[0]);
    }
    private boolean isValid(String tok) {
        String[] parts = tok.split("\\.", -1);
        if (parts.length != 4) return false;
        for (String p : parts) {
            if (p.isEmpty() || p.length() > 3) return false;
            for (char c : p.toCharArray()) if (!Character.isDigit(c)) return false;
            if (p.length() > 1 && p.charAt(0) == '0') return false;
            if (Integer.parseInt(p) > 255) return false;
        }
        return true;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> findValidIpAddresses(string rootPath, vector<vector<string>>& files) {
        string prefix = rootPath;
        if (prefix.empty() || prefix.back() != '/') prefix += '/';
        vector<string> out;
        auto valid = [](const string& tok) {
            vector<string> parts; string cur;
            for (char c : tok) { if (c == '.') { parts.push_back(cur); cur.clear(); } else cur += c; }
            parts.push_back(cur);
            if (parts.size() != 4) return false;
            for (auto& p : parts) {
                if (p.empty() || p.size() > 3) return false;
                for (char c : p) if (!isdigit((unsigned char)c)) return false;
                if (p.size() > 1 && p[0] == '0') return false;
                if (stoi(p) > 255) return false;
            }
            return true;
        };
        for (auto& f : files) {
            if (f[0].rfind(prefix, 0) != 0) continue;
            stringstream ss(f[1]); string tok;
            while (ss >> tok) if (valid(tok)) out.push_back(tok);
        }
        sort(out.begin(), out.end());
        return out;
    }
};