LeetCode #10

本贴最后更新于 2201 天前,其中的信息可能已经东海扬尘

问题:模拟正则表达式中的.和 *

'.' 匹配任意单个字符。
'*' 匹配零个或多个前面的元素。

匹配应该覆盖整个字符串 (s) ,而不是部分字符串。

说明:

  • s 可能为空,且只包含从 a-z 的小写字母。
  • p 可能为空,且只包含从 a-z 的小写字母,以及字符 .*

解答:
这是比较困难的一道题。官方中文站的通过率只有不到 1/4。其实想清楚正则的匹配过程也不难。主要有以下几点:
0. 正则匹配以正则单元为单位,普通字符也算正则单元,特殊的,如果有*,则其与前一个字符结合为一个正则单元。

  1. java 的正则表达式是 NFA,默认是贪婪匹配,也就是说每个正则单元(记为 pi)会尽可能多的匹配目标字符串(s)。
  2. 当前正则单元存在*时,既可尝试匹配当前目标字符也可跳到下一个单元,默认是尝试匹配。
  3. 如若当前单元不匹配,则回退到上一次存在匹配分岔的位置(状态)去尝试。
  4. 如若模式和字符串都匹配完了,则匹配成功。
  5. 如若字符串匹配完了,正则式无法匹配完则失败,反之亦然。
  6. 如没有可退回的位置,则匹配失败。
  7. 注意边界情况。

如果想系统学习正则表达式可找《精通正则表达式》这本书来看看,力荐。

这里用一个链表模拟栈,记录每次分岔的状态(下次可尝试匹配的状态)

package xyz.quxiao.play.lab.leetcode;

import java.util.AbstractMap.SimpleEntry;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;

/**
 * @author 作者 :quxiao 创建时间:2018/9/3 22:39
 */public class Problem10 {

  public static void main(String[] args) {
    Problem10 problem10 = new Problem10();
//    System.out.println(problem10.isMatch("abcda", ".*a.*c*da"));
//    System.out.println(problem10.isMatch("aa", "a*"));
//    System.out.println(problem10.isMatch("aab", "c*a*b"));
//    System.out.println(problem10.isMatch("aab", ".*"));
//    System.out.println(problem10.isMatch("mississippi", "mis*is*p*."));
//    System.out.println(problem10.isMatch("abc", "abcc"));
//    System.out.println(problem10.isMatch("", "a*c*"));
//    System.out.println(problem10.isMatch("aac", ".*.*a*c"));
  System.out.println(problem10.isMatch("aacd", ".*.*a*c"));
    System.out.println(problem10.isMatch("", ""));
  }

  public boolean isMatch(String s, String p) {
    if (s == null) {
      s = "";
    }
    if (p == null) {
      p = "";
    }
    int star = "*".charAt(0);
    // 提取匹配单元
  List patternUnit = new ArrayList<>();
    for (int i = 0; i < p.length(); i++) {
      int j = i + 1;
      if (j < p.length() && p.charAt(j) == star) {
        patternUnit.add(p.substring(i, i + 2));
        i++;
      } else {
        patternUnit.add(p.substring(i, i + 1));
      }
    }
    // 
  LinkedList> matchQueue = new LinkedList<>();
    int i = 0;
    int j = 0;
    // 当还没匹配完时
  while (true) {
      if (i == s.length() && j == patternUnit.size()) {
        return true;
      }

      if (j == patternUnit.size()) {
        if (matchQueue.isEmpty()) {
          return false;
        } else {
          Entry pop = matchQueue.pop();
          i = pop.getKey();
          j = pop.getValue();
          continue;
        }
      }

      String pattern = patternUnit.get(j);
      String str = getChar(s, i);
      if (pattern.contains("*")) {
        matchQueue.add(0, new SimpleEntry<>(i, j + 1));
        if (unitMatch(str, pattern)) {
          // 推进
  i++;
          // 注意i可能因为向前推进导致超过边界,这里不分辨是否在边界上,超出时依然让j向前推进
  if (i >= s.length()) {
            j++;
          }
          continue;
        } else {
          if (matchQueue.isEmpty()) {
            return false;
          } else {
            Entry pop = matchQueue.pop();
            i = pop.getKey();
            j = pop.getValue();
            continue;
          }
        }
      } else {
        if (unitMatch(str, pattern)) {
          // 推进
  i++;
          j++;
          continue;
        } else {
          if (matchQueue.isEmpty()) {
            return false;
          } else {
            Entry pop = matchQueue.pop();
            i = pop.getKey();
            j = pop.getValue();
            continue;
          }
        }
      }
    }
  }

  private boolean unitMatch(String character, String unit) {
    if (unit.startsWith(".")) {
      return true;
    } else if (character == null && unit.contains("*")) {
      return true;
    } else if (character == null){
      return false;
    } else {
      return unit.startsWith(character);
    }
  }

  private String getChar(String s, int pos) {
    if (pos >= s.length()) {
      return null;
    }
    return s.substring(pos, pos + 1);
  }
}
  • 正则表达式

    正则表达式(Regular Expression)使用单个字符串来描述、匹配一系列遵循某个句法规则的字符串。

    31 引用 • 94 回帖
  • 算法
    416 引用 • 254 回帖 • 23 关注
  • 链表
    12 引用 • 6 回帖

相关帖子

回帖

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • 酷鸟浏览器

    安全 · 稳定 · 快速
    为跨境从业人员提供专业的跨境浏览器

    3 引用 • 59 回帖 • 27 关注
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    28 引用 • 108 回帖
  • CloudFoundry

    Cloud Foundry 是 VMware 推出的业界第一个开源 PaaS 云平台,它支持多种框架、语言、运行时环境、云平台及应用服务,使开发人员能够在几秒钟内进行应用程序的部署和扩展,无需担心任何基础架构的问题。

    5 引用 • 18 回帖 • 157 关注
  • Firefox

    Mozilla Firefox 中文俗称“火狐”(正式缩写为 Fx 或 fx,非正式缩写为 FF),是一个开源的网页浏览器,使用 Gecko 排版引擎,支持多种操作系统,如 Windows、OSX 及 Linux 等。

    8 引用 • 30 回帖 • 421 关注
  • V2EX

    V2EX 是创意工作者们的社区。这里目前汇聚了超过 400,000 名主要来自互联网行业、游戏行业和媒体行业的创意工作者。V2EX 希望能够成为创意工作者们的生活和事业的一部分。

    17 引用 • 236 回帖 • 349 关注
  • AngularJS

    AngularJS 诞生于 2009 年,由 Misko Hevery 等人创建,后为 Google 所收购。是一款优秀的前端 JS 框架,已经被用于 Google 的多款产品当中。AngularJS 有着诸多特性,最为核心的是:MVC、模块化、自动化双向数据绑定、语义化标签、依赖注入等。2.0 版本后已经改名为 Angular。

    12 引用 • 50 回帖 • 466 关注
  • 一些有用的避坑指南。

    69 引用 • 93 回帖
  • IPFS

    IPFS(InterPlanetary File System,星际文件系统)是永久的、去中心化保存和共享文件的方法,这是一种内容可寻址、版本化、点对点超媒体的分布式协议。请浏览 IPFS 入门笔记了解更多细节。

    21 引用 • 245 回帖 • 248 关注
  • OpenResty

    OpenResty 是一个基于 NGINX 与 Lua 的高性能 Web 平台,其内部集成了大量精良的 Lua 库、第三方模块以及大多数的依赖项。用于方便地搭建能够处理超高并发、扩展性极高的动态 Web 应用、Web 服务和动态网关。

    17 引用 • 50 关注
  • SEO

    发布对别人有帮助的原创内容是最好的 SEO 方式。

    35 引用 • 200 回帖 • 17 关注
  • Tomcat

    Tomcat 最早是由 Sun Microsystems 开发的一个 Servlet 容器,在 1999 年被捐献给 ASF(Apache Software Foundation),隶属于 Jakarta 项目,现在已经独立为一个顶级项目。Tomcat 主要实现了 JavaEE 中的 Servlet、JSP 规范,同时也提供 HTTP 服务,是市场上非常流行的 Java Web 容器。

    162 引用 • 529 回帖 • 3 关注
  • Markdown

    Markdown 是一种轻量级标记语言,用户可使用纯文本编辑器来排版文档,最终通过 Markdown 引擎将文档转换为所需格式(比如 HTML、PDF 等)。

    167 引用 • 1491 回帖 • 3 关注
  • 爬虫

    网络爬虫(Spider、Crawler),是一种按照一定的规则,自动地抓取万维网信息的程序。

    106 引用 • 275 回帖 • 1 关注
  • ZeroNet

    ZeroNet 是一个基于比特币加密技术和 BT 网络技术的去中心化的、开放开源的网络和交流系统。

    1 引用 • 21 回帖 • 630 关注
  • Redis

    Redis 是一个开源的使用 ANSI C 语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value 数据库,并提供多种语言的 API。从 2010 年 3 月 15 日起,Redis 的开发工作由 VMware 主持。从 2013 年 5 月开始,Redis 的开发由 Pivotal 赞助。

    285 引用 • 248 回帖 • 105 关注
  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    540 引用 • 672 回帖
  • Scala

    Scala 是一门多范式的编程语言,集成面向对象编程和函数式编程的各种特性。

    13 引用 • 11 回帖 • 117 关注
  • 大数据

    大数据(big data)是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。

    93 引用 • 113 回帖
  • HTML

    HTML5 是 HTML 下一个的主要修订版本,现在仍处于发展阶段。广义论及 HTML5 时,实际指的是包括 HTML、CSS 和 JavaScript 在内的一套技术组合。

    103 引用 • 295 回帖 • 2 关注
  • 电影

    这是一个不能说的秘密。

    120 引用 • 598 回帖
  • 钉钉

    钉钉,专为中国企业打造的免费沟通协同多端平台, 阿里巴巴出品。

    15 引用 • 67 回帖 • 354 关注
  • 招聘

    哪里都缺人,哪里都不缺人。

    190 引用 • 1056 回帖
  • 笔记

    好记性不如烂笔头。

    308 引用 • 793 回帖
  • WordPress

    WordPress 是一个使用 PHP 语言开发的博客平台,用户可以在支持 PHP 和 MySQL 数据库的服务器上架设自己的博客。也可以把 WordPress 当作一个内容管理系统(CMS)来使用。WordPress 是一个免费的开源项目,在 GNU 通用公共许可证(GPLv2)下授权发布。

    65 引用 • 113 回帖 • 265 关注
  • WebSocket

    WebSocket 是 HTML5 中定义的一种新协议,它实现了浏览器与服务器之间的全双工通信(full-duplex)。

    48 引用 • 206 回帖 • 369 关注
  • 前端

    前端技术一般分为前端设计和前端开发,前端设计可以理解为网站的视觉设计,前端开发则是网站的前台代码实现,包括 HTML、CSS 以及 JavaScript 等。

    247 引用 • 1347 回帖 • 1 关注
  • Notion

    Notion - The all-in-one workspace for your notes, tasks, wikis, and databases.

    5 引用 • 26 回帖