算法：字符串匹配问题

Question

import java.util.HashMap;

import java.util.Map;

public class TestMap {

    public static void main(String[] args) {

        Map<String, String> map = new HashMap<>();

        map.put("1", "1");

        map.put("21", "1");

        map.put("22", "1");

        map.put("23", "1");

        map.put("24", "1");

        map.put("25", "1");

        map.put("26", "1");

        map.put("27", "1");

        map.put("28", "1");

        map.put("29", "1");

        map.put("311", "1");

        map.put("312", "1");

        map.put("313", "1");

        map.put("314", "1");

        map.put("315", "1");

        map.put("316", "1");

        map.put("317", "1");

        map.put("318", "1");

        map.put("319", "1");

        map.put("321", "1");

        map.put("322", "1");

        map.put("323", "1");

        map.put("324", "1");

        map.put("325", "1");

        map.put("326", "1");

        map.put("327", "1");

        map.put("328", "1");

        map.put("329", "1");

        map.put("331", "1");

        map.put("332", "1");

        map.put("333", "1");

        map.put("334", "1");

        map.put("335", "1");

        map.put("336", "1");

        map.put("337", "1");

        map.put("338", "1");

        map.put("339", "1");

        String str = "3333333333";

        for (int i=0; i<str.length(); i++) {

            String res = map.get(str.substring(0, i));

            System.out.println(res);

        }

    }

}

有如上测试类，map中的key的规则是长的key从首字符开始不包含完整的短的key，然后给定一个字符串，从第一个字符匹配到最优的map的值，有没有更好的算法？

算法描述：现有上百万条长短不一的key，key的规则是长的key从首字符开始不包含完整的短的key，比如说key(21)不包含key(1),key(321)不包含key(3,32)等，然后给定一个字符串从首字符开始最优匹配，比如说有字符串222，最后在给定的key（21,22，23）中匹配22，要计算量小，速度快的算法。

Answer 1

可以用treemap实现NavigableMap<String, String> map = new TreeMap<>();&nbsp; &nbsp; &nbsp; &nbsp; map.put("11","1");&nbsp; &nbsp; &nbsp; &nbsp; map.put("21","1");&nbsp; &nbsp; &nbsp; &nbsp; map.put("22","1");&nbsp; &nbsp; &nbsp; &nbsp; map.put("23","1");&nbsp; &nbsp; &nbsp; &nbsp; map.put("24","1");&nbsp; &nbsp; &nbsp; &nbsp; map.put("25","1");&nbsp; &nbsp; &nbsp; &nbsp; map.put("26","1");&nbsp; &nbsp; &nbsp; &nbsp; map.put("27","1");&nbsp; &nbsp; &nbsp; &nbsp; map.put("28","1");&nbsp; &nbsp; &nbsp; &nbsp; map.put("29","1");&nbsp; &nbsp; &nbsp; &nbsp; String lowerKey = map.lowerKey("114");&nbsp; &nbsp; &nbsp; &nbsp; System.out.println(StringUtils.startsWith("114", lowerKey) ? lowerKey : null);