URL高效匹配算法如何实现？

Question

项目想通过URL来实现接口鉴权，用户下可以查询到能访问的URL列表，但是URL可能是一个正则表达式，如下所示，某个用户的URL列表，表示用户可以访问
/aa/bb,/aa/cc,和/bb下所有的接口。

/aa/bb
/aa/cc
/bb/**

Answer 1

import lombok.Data;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @ClassName: TestPath
 * @Description: TODO
 * @Author: wuzhiyong
 * @Time: 2022/2/8 10:57
 * @Version: v1.0
 **/
public class TestPath {
    public static void main(String[] args) {
        List<String> paths = new ArrayList<>();
        paths.add("/a/a/vv/vv/d");
        paths.add("/b/a/ss/vv/d");
        paths.add("/c/b/*/vv/d");
        paths.add("/a/a/vv/ss/d");
        paths.add("/b/a/vv/vv/d");
        paths.add("/c/a/vv/vv/d");
        TreeNode root = generateTree(paths);
        root.print("");
//        long start = System.currentTimeMillis();
//        long n = 100000000;
//        while (n > 0) {
//            isPass(root, "/c/b/vv/vv/d");
//            n--;
//        }
//        System.out.println(100000000 / (System.currentTimeMillis() - start));
    }

    public static boolean isPass(TreeNode root, String path) {
        String[] vars = path.replaceFirst("/", "").split("/");
        TreeNode node = root;
        for (String var : vars) {
            if (node.getChilds().containsKey(var)) {
                node = node.getChilds().get(var);
                continue;
            }
            if (node.getChilds().containsKey("*")) {
                node = node.getChilds().get("*");
                continue;
            }
            return false;
        }
        return true;
    }

    public static TreeNode generateTree(List<String> paths) {
        TreeNode root = new TreeNode();
        for (String path : paths) {
            insertTree(root, path);
        }
        return root;
    }

    public static void insertTree(TreeNode root, String path) {
        String[] vars = path.replaceFirst("/", "").split("/");
        TreeNode node = root;
        for (String tmp : vars) {
            if (!node.getChilds().containsKey(tmp)) {
                TreeNode tmpNode = new TreeNode();
                node.getChilds().put(tmp, tmpNode);

            }
            node = node.getChilds().get(tmp);
        }
    }
}

@Data
class TreeNode {
    private Map<String, TreeNode> childs = new HashMap();

    public void addChild(String key, TreeNode node) {
        this.childs.put(key, node);
    }

    public boolean isExist(String key) {
        return childs.containsKey(key);
    }

    public TreeNode getNode(List<String> keys) {
        TreeNode tmp = this;
        for (String key : keys) {
            tmp = tmp.getChilds().get(key);
        }
        return tmp;
    }

    public void print(String cpt) {
        if (childs.size() == 0) {
            System.out.println(cpt);
        } else {
            for (String key : childs.keySet()) {
                childs.get(key).print(cpt + "/" + key);
            }
        }
    }
}