H5W3
当前位置:H5W3 > 其他技术问题 > 正文

算法:字符串匹配问题

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,要计算量小,速度快的算法。

回答:

试试看字典树(Trie)?

https://en.wikipedia.org/wiki…

回答:

可以用treemap实现

NavigableMap<String, String> map = new TreeMap<>();
        map.put("11","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");

        String lowerKey = map.lowerKey("114");
        System.out.println(StringUtils.startsWith("114", lowerKey) ? lowerKey : null);

本文地址:H5W3 » 算法:字符串匹配问题

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址