匹配路径

谁践踏了优雅 2022-06-08 08:54 184阅读 0赞

> 题目：假如有一个HTTP Server，可以对不同的路径（Path）注册不同的处理函数（Handler）。路径的格式为/x/y/z，使用“/”作为分隔符，被分隔开的每个组件都是只包含字母的非空字符串；路径总是以“/”开头，且不以“/”结尾，也不会出现“/x//y”这样的情况。为了简化问题，我们将处理函数用整数的ID号表示。  
> 对于客户端的HTTP请求，我们需要根据路径匹配最合适的处理函数。匹配规则是：在所有已经注册的路径中，找到包含该路径的最长前缀。前缀要求对组件的匹配是完整的，因此“/a/b”是“/a/b/c”的前缀，但不是“/a/bc”的前缀。
> 
> 输入：输入分两部分：  
> 第一部分是注册的路径列表，每行两个元素，用空格分开，分别为路径和ID号；ID号为非0整数，且不会重复。  
> 第二部分是需要匹配的路径列表，每行一个路径。  
> 两个部分用只包含一个短横线的特殊行分隔。
> 
> 输出：对于每个需要匹配的路径，输出其匹配的ID号，每行一个；如果没有找到匹配路径，则输出0

例：  
输入

> /a 1  
> /a/b 2  
> /a/b/c/d/e/f/g/h/i 3  
> /a/bcde 4  
> *-*  
> /a  
> /a/b  
> /a/b/c/d  
> /a/b/c/d/e/f/g/h/i  
> /a/bcde  
> /a/bcdefghi  
> /b

输出

> 1  
> 2  
> 2  
> 3  
> 4  
> 1  
> 0

*–*  
此题的解题关键在于在路径后加‘/’，然后将该注册路径与需要匹配的路径进行匹配，用到String的substring(beginIndex, endIndex)方法

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Map.Entry;
    import java.util.Scanner;
    
    public class PathPipei {
        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);
            Map<Integer, String> map = new HashMap<>();
            ArrayList<String> list = new ArrayList<>();
            while(in.hasNext()){
                String s = in.nextLine();
                if(s.equals("-"))
                    break;
                map.put(Integer.valueOf(s.split(" ")[1]), s.split(" ")[0]);
            }
            while(in.hasNextLine()){
                String s = in.nextLine();
                if(s.isEmpty())
                    break;
                list.add(s);
            }
            isMatch(map, list);
        }
        private static void isMatch(Map<Integer, String> map, ArrayList<String> list){
            for (String string : list) {
                //记录最大匹配长度
                int max = 0;
                //记录map的key
                int index = -1;
                //匹配路径后加“/”
                StringBuilder builder1 = new StringBuilder(string);
                builder1.append("/");
                for (Entry<Integer, String> entry : map.entrySet()) {
                    //注册路径下加“/”
                    StringBuilder builder = new StringBuilder(entry.getValue());
                    builder.append("/");
                    //如果匹配的话，更新最大匹配长度和key
                    if(builder1.length() >= builder.length() && builder1.toString().substring(0, builder.toString().length()).equals(builder.toString())){
                        if(max < builder.toString().length()){
                            max = builder.toString().length();
                            index = entry.getKey();
                        }
                    }
                }
                if(max != 0)
                    System.out.println(index);
                else
                    System.out.println("0");
    
            }
        }
    }