LeetCode #10

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

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

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

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

说明:

解答:
这是比较困难的一道题。官方中文站的通过率只有不到 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)使用单个字符串来描述、匹配一系列遵循某个句法规则的字符串。

    24 引用 • 88 回帖
  • 算法
    311 引用 • 235 回帖 • 16 关注
  • 链表
    8 引用 • 6 回帖
回帖
请输入回帖内容...