文档章节

一道笔试题

芝麻糖葫芦
 芝麻糖葫芦
发布于 2017/05/18 21:23
字数 428
阅读 25
收藏 0

下午面试遇到一道笔试题,题目是编写一个支持部分正则表达式的解析器,获取目标字符串在原字符串中第一次出现的索引,例如 查找“ava”在“Lear Java.”中第一次出现的索引为6

其中“.”代表任意单个字符,“^”代表从字符串的开头开始匹配,“$”匹配字符串的结尾,“*”匹配任意个字符

因为在其他笔试题中浪费了太多时间,没有写出这部分代码,回家路上有了思路,现在记录下来。

/**
 * 主要的工具类
 * Created by Morven on 2017/5/18.
 */
public class RegularMacher {
    private RegularMacher() {}

    private static class RegularMacherHolder {
        private static RegularMacher instance = new RegularMacher();
    }

    public static RegularMacher getInstance() {
        return RegularMacherHolder.instance;
    }

    public int matchIndex(String source, String regular) {
        char[] chars = regular.toCharArray();
        for (int i = 0; i < source.length(); i++) {
            int index = indexOf(source, i, chars, 0);
            if (index > -1) return index;
        }
        return -1;
    }

    private int indexOf(String source, int beginIndex, char[] chars, int charIndex) {
        char c = chars[charIndex];
        if (c == '^') {
            if (beginIndex > 0) {
                return -1;
            }
            int index = indexOf(source, beginIndex, chars, charIndex + 1);
            if (index > -1) {
                return beginIndex;
            }
            return -1;
        } else if (c == '$') {
            if (beginIndex < source.length()) {
                return -1;
            }
            return beginIndex;
        } else if (c == '.') {
        } else if (c == '*') {
            if (charIndex + 1 == chars.length) {
                return beginIndex;
            }
            if (charIndex + 2 == chars.length && chars[charIndex + 1] == '$') {
                return beginIndex;
            }
            for (int i = beginIndex; i < source.length(); i++) {
                int index = indexOf(source, i, chars, charIndex + 1);
                if (index > -1) return index;
            }
            return -1;
        } else {
            if (c != source.charAt(beginIndex)) {
                return -1;
            }
        }
        if (charIndex + 1 == chars.length) return beginIndex;
        if (beginIndex + 1 == source.length()) {
            if (charIndex + 2 < chars.length) return -1;
        }
        int index = indexOf(source, beginIndex + 1, chars, charIndex + 1);
        if (index > -1) {
            return beginIndex;
        }
        return -1;
    }
}

/**
 * 测试
 * Created by Morven on 2017/5/18.
 */
public class RegularMacherTest {
    public static void main(String[] args) {
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", ".est"));//0
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", ".ssdfa"));//-1
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", "^.aa"));//-1
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", "*"));//0
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", "*$"));//0
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", "j*i"));//5
        System.out.println(RegularMacher.getInstance().matchIndex("Test java in Action.", "j*ava"));//5
    }
}

© 著作权归作者所有

共有 人打赏支持
芝麻糖葫芦
粉丝 3
博文 20
码字总数 5204
作品 0
济南
高级程序员
私信 提问

暂无文章

day152-2018-11-19-英语流利阅读-待学习

外媒看吴亦凡刷榜事件 Lala 2018-11-19 1.今日导读 近日,吴亦凡的专辑在国外陷入了刷榜风波,他的新专辑霸占了单曲榜前三名,并且前十名他占据了七席,力压美国乐坛巨星 Lady Gaga 和 A 妹,...

飞鱼说编程
29分钟前
5
0
开源 java CMS - FreeCMS2.8 微信管理 群发图文消息

项目地址:http://www.freeteam.cn/ 群发图文消息 管理员可以在这里群发图文消息 此列表只提取已审核并且带信息图片的数据! 选择需要群发的消息,点击“群发图文消息”按钮。 微信的限定: ...

freeteam
38分钟前
1
0
Beautiful Soup

定义 Python中的一个库,主要用于从网页爬取数据; 安装 pip install beautifulsoup4 四大对象 Beautiful Soup将复杂的HTML文档转换成树形结构,树中的每个节点都是Python对象,对象可归纳为...

村雨1943
49分钟前
4
0
Visual Studio 昨日发布新版本:增加实时同步编程、共同调试

多名开发者可以在同一个项目中编程,在编写代码和调试代码时只需发送一个 URL 网址,就能邀请他人参与协作,而且无需重新配置开发环境和安装任何附加包。该服务支持 Windows、Mac 与 Linux ...

linuxCool
52分钟前
5
0
发现一种不错的学习方法

这是在《软技能,代码之外的生存之道》所看到的一种学习方法,感觉这个理念不错,分享出来,共勉。 我的「十步学习法」 多年以来,我都承受着巨大的压力:快速学习新技术、新编程语言、新框架...

firepation
52分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部