Happywzy~ 2021-08-16 10:27 采纳率: 100%
浏览 108
已结题

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

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

/aa/bb
/aa/cc
/bb/**
  • 写回答

2条回答 默认 最新

  • Happywzy~ 2022-02-08 14:40
    关注
    
    
    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);
                }
            }
        }
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 2月25日
  • 已采纳回答 2月17日
  • 修改了问题 2月8日
  • 创建了问题 8月16日

悬赏问题

  • ¥15 MATLAB动图问题
  • ¥15 有段代码不知道怎么理解,const isToken = (config.headers || {}).isToken === false
  • ¥15 我的显卡支持CUDA最高版本是12.3,这个版本也支持VS 2022 17.0这种情况下如果我想下载CUDA11.8,需要下载旧版本的VS2022吗
  • ¥100 采用栈和深度优先算法对我的代码进行修改显示路径
  • ¥15 pointnet2包安装
  • ¥20 射频功率问题,解答者有酬谢!
  • ¥80 构建降雨和积水的预测模型
  • ¥15 #Qt Transform setTransform()在鼠标拖动移动视角是一致在原地不动,无法变换视角(细微观察似乎视图有在原地抖动),无法变换视角(细微观察似乎视图有在原地抖动)
  • ¥50 如何利用无人机拍摄的数码照片测量鸟卵的长短径
  • ¥100 github贡献者给与奖励